Aligning optical maps to de Bruijn graphs
Authors:
- 30 January 2019
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 35 (18) , 3250-3256
Abstract
Optical maps are high-resolution restriction maps (Rmaps) that give a unique numeric representation to a genome. Used in concert with sequence reads, they provide a useful tool for genome assembly and for discovering structural variations and rearrangements. Although they have been a regular feature of modern genome assembly projects, optical maps have been mainly used in post-processing step and not in the genome assembly process itself. Several methods have been proposed for pairwise alignment of single molecule optical maps—called Rmaps, or for aligning optical maps to assembled reads. However, the problem of aligning an Rmap to a graph representing the sequence data of the same genome has not been studied before. Such an alignment provides a mapping between two sets of data: optical maps and sequence data which will facilitate the usage of optical maps in the sequence assembly step itself. We define the problem of aligning an Rmap to a de Bruijn graph and present the first algorithm for solving this problem which is based on a seed-and-extend approach. We demonstrate that our method is capable of aligning 73% of Rmaps generated from the Escherichia coli genome to the de Bruijn graph constructed from short reads generated from the same genome. We validate the alignments and show that our method achieves an accuracy of 99.6%. We also show that our method scales to larger genomes. In particular, we show that 76% of Rmaps can be aligned to the de Bruijn graph in the case of human data. The software for aligning optical maps to de Bruijn graph, omGraph is written in C++ and is publicly available under GNU General Public License at https://github.com/kingufl/omGraph. Supplementary data are available at Bioinformatics online.Keywords
Funding Information
- National Science Foundation (1618814)
- Research Council of Finland (308030, 314170)
This publication has 34 references indexed in Scilit:
- AGORA: Assembly Guided by Optical Restriction AlignmentBMC Bioinformatics, 2012
- SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell SequencingJournal of Computational Biology, 2012
- High-resolution human genome structure by single-molecule analysisProceedings of the National Academy of Sciences, 2010
- ABySS: A parallel assembler for short read sequence dataGenome Research, 2009
- Scaffolding and validation of bacterial genome assemblies using optical restriction mapsBioinformatics, 2008
- Velvet: Algorithms for de novo short read assembly using de Bruijn graphsGenome Research, 2008
- ALLPATHS: De novo assembly of whole-genome shotgun microreadsGenome Research, 2008
- An algorithm for assembly of ordered restriction maps from single DNA moleculesProceedings of the National Academy of Sciences, 2006
- BLAT—The BLAST-Like Alignment ToolGenome Research, 2002
- Basic local alignment search toolJournal of Molecular Biology, 1990