Université de Rennes 1 Haplotype phasing from long reads with ASP : a flexible optimization approach Phasage d’haplotypes par ASP à partir de longues lectures : une approche d’optimisation flexible Bioinformatiquephasage d’haplotypepolyploïdeséquençage longues lecturesclusteringoptimisationAnswer Set Programming Bioinformaticshaplotype phasingpolyploidlong read sequencingclusteringoptimizationAnswer set programming Bioinformatique Haplotype Chaque chromosome d’organisme di- ou polyploïde présente plusieurs haplotypes, qui sont fortement similaires mais divergent sur un certain nombre de positions. Cependant, la majorité des génomes de référence ne renseignent qu’une seule séquence pour chaque chromosome, et ne reflètent donc pas la réalité biologique. Or, il est crucial d’avoir accès à ces informations, qui sont utiles en médecine, en agronomie ou encore dans l’étude des populations. Le récent développement des technologies de troisième génération, notamment des séquenceurs PacBio et Oxford Nanopore Technologies, a permis la production de lectures longues facilitant la reconstruction des séquences d’haplotypes. Il existe pour cela des méthodes bioinformatiques, mais elles ne fournissent qu’une unique solution. Cette thèse propose une méthode de phasage d’haplotype basée sur la recherche de composantes connexes dans un graph de similarité des lectures pour identifier les haplotypes. Cette méthode utilise l’Answer Set Programming pour travailler sur l’ensemble des solutions optimales. L’algorithme de phasage a permis de reconstruire les haplotypes du rotifère diploïde Adineta vaga. Each chromosome of a di- or polyploid organism has several haplotypes, which are highly similar but diverge on a certain number of positions. However, most of the reference genomes only provide a single sequence for each chromosome, and therefore do not reflect the biological reality. Yet, it is crucial to have access to this information, which is useful in medicine, agronomy and population studies. The recent development of third generation technologies, especially PacBio and Oxford Nanopore Technologies sequencers, has allowed for the production of long reads that facilitate haplotype sequence reconstruction. Bioinformatics methods exist for this task, but they provide only a single solution. This thesis introduces an approach for haplotype phasing based on the search of connected components in a read similarity graph to identify haplotypes. This method uses Answer Set Programming to work on the set of optimal solutions. This phasing algorithm has been used to reconstruct haplotypes of the diploid rotifer Adineta vaga. Electronic Thesis or DissertationText en application/pdf1 : 9591 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/c21ce466-013d-4ee6-9721-0109af7f9249 Delahaye Clara 1997-05-26 FR 269119647 delahaye.clara@orange.fr 2022REN1S093 http://www.theses.fr/2022REN1S093 2022-12-15 Informatique Universite de Rennes 1thesis.degree.grantor_1 02778715X Doctorat non ouiNicolasJacquesintervenant_1116276142LavenierDominiqueintervenant_206011911XFerréSébastienintervenant_306939685XFriedrichAnneintervenant_5128643811FlotJean-Françoisintervenant_4118971387KlauGunnarintervenant_6269120009 MATHSTICecoleDoctorale_1 204770424 IRISA partenaireRecherche_1 026386909 ddc:004 NicolasJacquesLavenierDominiqueFerréSébastienFlotJean-FrançoisFriedrichAnneKlauGunnarUniversite de Rennes 1Sciences et technologie, medecine, pharmacie, odontologie, droit, economie, gestion, philosophieMATHSTICÉcole doctorale Mathématiques et sciences et technologies de l'information et de la communication (Rennes) IRISA ASCII PDF 9820819