DNA fragments positioning improvement to realise consensus sequences in the de novo long reads assembly context
Amélioration du positionnement de fragments ADN pour réalisation de séquences consensus dans le contexte de l’assemblage de novo de longues lectures
Résumé
DNA molecular in silico analysis requires sequencing it in fragments called reads, and then assembling them. Today’s, long reads sequencing technologies offer the possibility to overcome genome’s repeated regions issues with being entirely covered, but product high errors rate data with sequencing errors, like nucleotides insertions or deletions,
called indels. De novo assembly is an assembly without using a reference. Although some assemblers already exist according to several methods - as using De Bruijn graphs or by correcting iteratively the reads for example, we propose a two steps strategy : first, we attribute to the maximum of reads a position on a same positions axis and then we
product a consensus sequence thanks to the positioning. At these aims, we propose a modelling for the positioning issue with the mixed integer linear programming (MILP), and we present first ideas for the consensus sequences production with MILP too and multiple sequences alignment from the positioning. As the final aim of this strategy is
to formalize the genome assembly issue, we structured it according the mathematical method, that permits to target methodological choices precisely, and then reducing the heuristic uses. Finally, we tested the strategy with bacteria genomes. Despite the fact that positioning results show positive ones, the consensus results are less positive but don’t
remove the potentiality of the associated methods.
L’analyse in silico d’une molécule d’ADN requiert son séquençage en fragments appelés lectures puis leur assemblage. Les technologies de séquençage produisant de longues lectures offrent l’avantage de surpasser les problèmes de régions répétées dans les génomes qui sont alors plus facilement couvertes dans leur entièreté, mais produisent des lectures avec un fort taux d’erreurs qui se réfèrent davantage à des insertions ou des suppressions de nucléotides, nommées indels. L’assemblage de novo est un assemblage qui ne s’aide d’aucune référence. Bien que des méthodes d’assemblage de longues lectures ont déjà été proposés, par l’usage de graphes de De Bruijn ou par correction successives des lectures par exemple, nous proposons une stratégie qui s’opère en deux étapes : positionner le maximum de lectures sur un axe de positions, puis produire une séquence consensus en s’aidant des positions déterminées. À ces
fins, nous proposons une modélisation du problème du positionnement avec la programmation mathématique linéaire mixte en nombres entiers (PLMNE), et présentons de premières idées pour la production de séquences consensus avec la PLMNE et l’alignement multiples de séquences à partir de ce positionnement. La finalité de cette stratégie étant de formaliser la problématique d’assemblage de génome, nous l’avons structurée selon la méthode mathématique, ce qui permet de cibler les choix méthodologiques précisément afin de réduire l’usage d’heuristiques. Enfin nous avons testé cette stratégie sur des génomes bactériens. Bien que les résultats de positionnements soient globalement très positifs, ceux pour le consensus le sont moins mais n’enlèvent pas aux méthodes leur potentialités.
Origine : Fichiers produits par l'(les) auteur(s)