Optimal Scaffolding for Chloroplasts' Inverted Repeats - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Optimal Scaffolding for Chloroplasts' Inverted Repeats

Scaffolding Optimal pour les Régions Répétées Inverses-Complémentaires de Génome de Chloroplastes

Résumé

Scaffolding step in the genome assembly aims to determine the order and the orientation of a huge number of previously assembled genomic fractions (contigs/scaffolds). Here we introduce a particular case of this problem and denote it by Nested Inverted Fragments Scaffolding (NIFS). We formulate it as an optimisation problem in a particular kind of directed graph that we call Multiplied Doubled Contigs Graph (MDCG). Furthermore, we prove that the NIFS problem is NP-Hard. We also discuss how the chloroplast data have been generated by filtering the reads sequenced both from plants and chloroplasts. Moreover, we propose a graph structure to visualise the solution and to highlight the particularity of chloroplast's regions structure.
Fichier principal
Vignette du fichier
JOBIM_2022_KhloraaScaf.pdf (499.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03625229 , version 1 (30-03-2022)

Identifiants

  • HAL Id : hal-03625229 , version 1

Citer

Victor Epain, Rumen Andonov, Dominique Lavenier. Optimal Scaffolding for Chloroplasts' Inverted Repeats. JOBIM2022, Jul 2022, Rennes, France. ⟨hal-03625229⟩
65 Consultations
38 Téléchargements

Partager

Gmail Facebook X LinkedIn More