[GENSCALE] Assemblage de fragments ADN : structures de graphes et échafaudage de génomes de chloroplastes

Titre : Assemblage de fragments ADN : structures de graphes et échafaudage de génomes de chloroplastes

L’accès du public à cette soutenance est contraint à une inscription préalable obligatoire auprès de pr%C3%A9nom [*] nominria [*] fr (victor[dot]epain[at]inria[dot]fr)  ou marie [*] le_roicinria [*] fr (marie[dot]le_roic[at]inria[dot]fr) – L’accès ne sera pas autorisé sans inscription préalable. Par ailleurs, les visiteurs ne porteront ni bagage ni sac.

Résumé :

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 cette thèse, 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.