Phasage d’haplotypes par ASP à partir de longues lectures : une approche d’optimisation flexible.

English version below

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.

Haplotype phasing from long reads with ASP: a flexible optimization approach.

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.