Assemblage de Novo de Longues Lectures Par Programmation Linéaire

EasyChair Preprint 2573, version 1

Abstract

Etudier in silico un génome nécessite deux principales tâches : le séquencer, en le clonant puis en le découpant en plusieurs lectures, puis assembler les lectures. Les erreurs de séquençage dépendent de la taille des lectures générées : le taux d'erreur pour les longues lectures est plus important que celui des courtes lectures. Toutefois, les longues lectures permettent de contrer les problèmes issus des régions génomiques répétées. L'assemblage de novo est une méthode qui n'a pas besoin de référence.
Le programme présenté loreas, a pour but d'être un assembleur de novo en deux étapes : la première consiste à donner un ordonnancement des longues lectures, la deuxième, réaliser une séquence consensus des lectures ordonnancées. Pour le moment, seule la première étape fut réalisée.
Alors que d'autres assembleurs de novo usent d'heuristiques et des graphes de De Bruijn, loreas est basé sur les similarités de chevauchements entre toutes les lectures. A cette fin, la programmation linéaire en nombres entiers permet de trouver le plus lourd chemin dans un graph G=(V,E,⋋), où V est l'ensemble des sommets qui sont les longues lectures, E l'ensemble des arcs représentant les chevauchements entre les longues lectures - pondérés par ⋋, la longueur de chevauchement.
Si le graphe précédent est trop important, l'ensemble V est partitionné en parties distinctes, puis toutes les parties sont résolues séquentiellement.
Dix génomes de bactéries simulés séquencés furent résolus pour la tâche d'ordonnancement des longues lectures. Il en résulte sept résultats positifs sur dix obtenus en moins de 12 minutes sur un ordinateur portable.

Keyphrases: Graphe de chevauchements, PLNE, partitionnement de graphe, problème du chemin de poids maximal

@booklet{EasyChair:2573,
  author    = {Victor Epain and Rumen Andonov and Hristo Djidjev and Dominique Lavenier},
  title     = {Long Reads Assembly Using Integer Linear Programming},
  howpublished = {EasyChair Preprint 2573},
  year      = {EasyChair, 2020}}