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.