PMSGA: A FAST DNA FRAGMENT ASSEMBLER

Juho Mäkinen, Jorma Tarhio, Sami Khuri

2010

Abstract

The DNA fragment assembly is an essential step in DNA sequencing projects. Since DNA sequencers output fragments, the original genome must be reconstructed from these small reads. In this paper, a new fragment assembly algorithm, Pattern Matching based String Graph Assembler (PMSGA), is presented. The algorithm uses multipattern matching to detect overlaps and a minimum cost flow algorithm to detect repeats. Special care was taken to reduce the algorithm's run time without compromising the quality of the assembly. PMSGA was compared with well-known fragment assemblers. The algorithm is faster than other assemblers. PMSGA produced high quality assemblies with prokaryotic data sets. The results for eukaryotic data are comparable with other assemblers.

Paper Citation

in Harvard Style

Mäkinen J., Tarhio J. and Khuri S. (2010). PMSGA: A FAST DNA FRAGMENT ASSEMBLER . In Proceedings of the First International Conference on Bioinformatics - Volume 1: BIOINFORMATICS, (BIOSTEC 2010) ISBN 978-989-674-019-1, pages 77-82. DOI: 10.5220/0002580800770082

in Bibtex Style

@conference{bioinformatics10,
author={Juho Mäkinen and Jorma Tarhio and Sami Khuri},
title={PMSGA: A FAST DNA FRAGMENT ASSEMBLER},
booktitle={Proceedings of the First International Conference on Bioinformatics - Volume 1: BIOINFORMATICS, (BIOSTEC 2010)},
year={2010},
pages={77-82},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002580800770082},
isbn={978-989-674-019-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Bioinformatics - Volume 1: BIOINFORMATICS, (BIOSTEC 2010)
TI - PMSGA: A FAST DNA FRAGMENT ASSEMBLER
SN - 978-989-674-019-1
AU - Mäkinen J.
AU - Tarhio J.
AU - Khuri S.
PY - 2010
SP - 77
EP - 82
DO - 10.5220/0002580800770082