J. Blazewicz, M. Kasprzak, M. Kierzynka, W. Frohmberg, A. Swiercz, P. Wojciechowski, P. Zurkowski
"Graph algorithms for DNA sequencing - origins, current models and the future"
European Journal of Operational Research
264 (2018) 799-812.
Download full text
— The final publication is available at Elsevier via
https://doi.org/10.1016/j.ejor.2016.06.043
Abstract:
With the ubiquitous presence of next-generation sequencing in modern
biological, genetic, pharmaceutical and medical research, not everyone pays
attention to the underlying computational methods. Even fewer researchers
know what were the origins of the current models for DNA assembly. We present
original graph models used in DNA sequencing by hybridization, discuss their
properties and connections between them. We also explain how these graph
models evolved to adapt to the characteristics of next-generation sequencing.
Moreover, we present a practical comparison of state-of-the-art DNA de novo
assembly tools representing these transformed models, i.e. overlap and
decomposition-based graphs. Even though the competition is tough, some
assemblers perform better and certainly large differences may be observed
in hardware resources utilization. Finally, we outline the most important
trends in the sequencing field, and try to predict their impact on the
computational models in the future.
Back to the List of publications
13 Oct 2017