Long Reads Assembly Using Integer Linear Programming

EasyChair Preprint no. 2573, version 2

Abstract

In silico studying a genome requires two steps: sequencing it with cloning and cutting the genome in several reads, and then, assembling the reads. It is well known that the number of sequencing errors is proportional to the reads' size. However, the use of long reads can be an advantage against genome repeated regions issues. De novo is an assembly method which does not use a reference.
The purpose of the described here tool, named loreas, is to be a de novo assembler in two tasks: first, ordering the long reads, and then, obtaining a consensus sequence of the ordered reads. Currently, only the first task was realised.
While other de novo long reads assemblers use heuristics and De Bruijn graphs, loreas is based on overlaps similarity between all the long reads. It uses integer linear programing, to find the heaviest path in a graph G=(V,E,⋋), where V is the vertices set corresponding to the long reads set, E the set of edges associated with the overlaps between long reads - weighted by ⋋: the overlap length.
When this graph is too huge, the set of reads V is partitioned in several parts. Then, all the parts are solved sequentially.
Here we present the solution concerning the first task related to ten bacteria genomes. Seven of them have been succefully solved for less than 12 minutes on a laptop.

Keyphrases: Graphe de chevauchements, partitionnement de graphe, PLNE, 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 no. 2573},

  year = {EasyChair, 2020}}