Université de Rennes Assemblage de fragments ADN : structures de graphes et échafaudage de génomes de chloroplastes DNA fragment assembly, graph structures and chloroplast genome scaffolding : comparative analyses, formulations and implementations Assemblage de génomesProgrammation linéaire en nombre entiersRépétitions génomiquesHaplotypes structuraux Genome assemblyInteger linear programmingGenome repeatsStructural haplotypes Chloroplastes Génome L’obtention de la séquence nucléotidique d’une molécule ADN nécessite sa fragmentation par des technologies de séquençage et l’assemblage des fragments. Ces fragments sont appelés lectures. Elles souffrent d’erreurs de séquençage et sont considérées sous deux orientations : celle de leur brin ADN d’origine ou l’inverse-complémentaire pour l’autre brin. L’assemblage se base sur des chevauchements deux à deux entre des lectures orientées, et est composé de trois phases : l’assemblage des lectures pour obtenir des contigs (des séquences plus longues que les lectures), l’échafaudage des contigs, pour obtenir des échafaudages (des ordres de contigs orientés), et la complétion des échafaudages (trouver les séquences de nucléotides séparant les contigs orientés dans les échafaudages). Dans ce manuscrit, nous comparons des structures de graphes représentant des relations de successions entre des séquences ADN orientées, utiles à différentes phases de l’assemblage. Puis, nous nous penchons sur le problème de l’échafaudage dédié aux génomes de chloroplastes en proposant une nouvelle formulation, une résolution exacte et une implémentation. To obtain the nucleotide sequence of a DNA molecule, the molecule is fragmented using a sequencing technology and the fragments are assembled. These fragments are called reads. They are subject to sequencing errors and must be considered in two orientations: that of their original DNA strand, or the reverse-complementary for the other strand. Assembly is based on pairwise overlaps between oriented reads and consists in three phases: assembling the reads to obtain contigs (sequences longer than the reads), scaffolding the contigs to obtain scaffolds (orders of oriented contigs), and completing the scaffolds (finding the nucleotide sequences separating the oriented contigs in the scaffolds). In this manuscript, we compare graph structures representing succession relations between oriented DNA sequences, useful at different phases of assembly. Then, we address the scaffolding problem dedicated to chloroplast genomes by proposing a new formulation, an exact resolution and an implementation. Electronic Thesis or DissertationText en application/pdf1 : 5351 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/e8fb7723-e57c-4c91-b5f3-3138081bdb18 Epain Victor 1997-04-04 FR 276523881 victor.epain@laposte.net 2023URENS083 http://www.theses.fr/2023URENS083 2023-11-27 Informatique Université de Rennesthesis.degree.grantor_1 26693823X Doctorat non ouiAndonovRumenintervenant_1110438221GibratJean-Françoisintervenant_2031134564FromontÉlisaintervenant_3095621601MarchetCamilleintervenant_4259182958LavenierDominiqueintervenant_506011911XWellerMathiasintervenant_6276524098AngelÉricintervenant_7154829870ChâteauAnnieintervenant_8227798856 MATISSEecoleDoctorale_1 267602553 IRISA partenaireRecherche_1 026386909 ddc:004 AndonovRumenGibratJean-FrançoisFromontÉlisaMarchetCamilleLavenierDominiqueWellerMathiasAngelÉricChâteauAnnieUniversité de RennesMATISSE IRISA ASCII PDF 5479482