GENOME CONTIGS ASSEMBLY METHOD BASED ON DE BRUJIN GRAPHS AND OVERLAP GRAPHS

Alexandrov Anton V., Sergey Kazakov, Sergey Melnikov, Sergushichev Alexey A. , Fedor Tsarev

2012 , VOLUME 12, NUMBER 6 ( November-December )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

GENOME CONTIGS ASSEMBLY METHOD BASED ON DE BRUJIN GRAPHS AND OVERLAP GRAPHS

A. V. Alexandrov, S. Kazakov, S. Melnikov, A. A. Sergushichev, F. Tsarev

Read the full article

Abstract

A method for genome contigs assembly is proposed. This method consists of two stages – quasicontigs assembly and contigs assembly. De Brujin graphs are used on the first stage and overlap graphs on the second one. The method was tested on Maylandia zebra fish genome containing nearly 1 billion nucleotides. Combining de Brujin graphs and overlap graphs makes this method much more space-efficient than the others.

Keywords: genome assembly, contigs, de Brujin graph, overlap graph

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License