Aligning optical maps to de Bruijn graphs

Show simple item record

dc.contributor University of Helsinki, Department of Computer Science en Mukherjee, Kingshuk Alipanahi, Bahar Kahveci, Tamer Salmela, Leena Boucher, Christina 2020-01-30T04:22:59Z 2021-09-03T02:45:34Z 2019-09-15
dc.identifier.citation 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 . en
dc.identifier.issn 1367-4803
dc.identifier.other PURE: 127484639
dc.identifier.other PURE UUID: 97c582b1-6cdd-42c0-83b4-19284f03afb5
dc.identifier.other WOS: 000487327500006
dc.identifier.other ORCID: /0000-0002-0756-543X/work/65310760
dc.description.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. en
dc.format.extent 7
dc.language.iso eng
dc.relation.ispartof Bioinformatics
dc.rights en
dc.subject GENOME en
dc.subject ALIGNMENT en
dc.subject SEQUENCE en
dc.subject ALGORITHM en
dc.subject SEARCH en
dc.subject 1182 Biochemistry, cell and molecular biology en
dc.subject 113 Computer and information sciences en
dc.title Aligning optical maps to de Bruijn graphs en
dc.type Article
dc.description.version Peer reviewed
dc.type.uri info:eu-repo/semantics/other
dc.type.uri info:eu-repo/semantics/acceptedVersion

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 simple item record