Aligning optical maps to de Bruijn graphs

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://hdl.handle.net/10138/310638

Lähdeviite

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 . https://doi.org/10.1093/bioinformatics/btz069

Julkaisun nimi: Aligning optical maps to de Bruijn graphs
Tekijä: Mukherjee, Kingshuk; Alipanahi, Bahar; Kahveci, Tamer; Salmela, Leena; Boucher, Christina
Muu tekijä: University of Helsinki, Department of Computer Science
Päiväys: 2019-09-15
Kieli: eng
Sivumäärä: 7
Kuuluu julkaisusarjaan: Bioinformatics
ISSN: 1367-4803
URI: http://hdl.handle.net/10138/310638
Tiivistelmä: 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.
Avainsanat: ORDERED RESTRICTION MAPS
GENOME
ALIGNMENT
SEQUENCE
ALGORITHM
SEARCH
1182 Biochemistry, cell and molecular biology
113 Computer and information sciences
Tekijänoikeustiedot:


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
main_short.pdf 1.353MB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot