J. Blazewicz, M. Bryja, M. Figlerowicz, P. Gawron, M. Kasprzak,
E. Kirton, D. Platt, J. Przybytek, A. Swiercz, L. Szajkowski
"Whole genome assembly from 454 sequencing output via modified DNA graph concept"
Computational Biology and Chemistry
33 (2009) 224-230.
Abstract:
Recently, 454 Life Sciences Corporation proposed a new biochemical approach to DNA sequencing (the
454 sequencing). It is based on the pyrosequencing protocol. The 454 sequencing aims to give reliable
output at a low cost and in a short time. The produced sequences are shorter than reads produced by
classical methods. Our paper proposes a new DNA assembly algorithm which deals well with such data
and outperforms other assembly algorithms used in practice.
The constructed SR-ASM algorithm is a heuristic method based on a graph model, the graph being a
modified DNA graph proposed for DNA sequencing by hybridization procedure. Other new features of
the assembly algorithm are, among others, temporary compression of input sequences, and a new and
fast multiple alignment heuristics taking advantage of the way the output data for the 454 sequencing
are presented and coded. The usefulness of the algorithm has been proved in tests on raw data generated
during sequencing of the whole 1.84Mbp genome of Prochlorococcus marinus bacteria and also
on a part of chromosome 15 of Homo sapiens. The source code of SR-ASM can be downloaded from
http://bio.cs.put.poznan.pl/ in the section 'Current research / DNA Assembly'.
Among publicly available assemblers our algorithm appeared to generate the best results, especially
in the number of produced contigs and in the lengths of the contigs with high similarity to the genome
sequence.
Back to the List of publications
18 Jun 2009