Aligning optical maps to de Bruijn graphs

Show full item record



Mukherjee , K , Alipanahi , B , Kahveci , T , Salmela , L & Boucher , C 2019 , ' Aligning optical maps to de Bruijn graphs ' , Bioinformatics , vol. 35 , no. 18 , pp. 3250-3256 .

Title: Aligning optical maps to de Bruijn graphs
Author: Mukherjee, Kingshuk; Alipanahi, Bahar; Kahveci, Tamer; Salmela, Leena; Boucher, Christina
Contributor: University of Helsinki, Department of Computer Science
Date: 2019-09-15
Language: eng
Number of pages: 7
Belongs to series: Bioinformatics
ISSN: 1367-4803
Abstract: Motivation: 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. Results: 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.
1182 Biochemistry, cell and molecular biology
113 Computer and information sciences

Files in this item

Total number of downloads: Loading...

Files Size Format View
main_short.pdf 1.353Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record