Download PDFOpen PDF in browser
FR
Switch back to the title and the abstract
in French

Long Reads Assembly Using Integer Linear Programming

EasyChair Preprint 2573, version 2

Versions: 12history
2 pagesDate: February 7, 2020

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, PLNE, partitionnement de graphe, problème du chemin de poids maximal

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser