Aligning optical maps to de Bruijn graphs

Visa fullständig post



Permalänk

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

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

Titel: Aligning optical maps to de Bruijn graphs
Författare: Mukherjee, Kingshuk; Alipanahi, Bahar; Kahveci, Tamer; Salmela, Leena; Boucher, Christina
Medarbetare: University of Helsinki, Department of Computer Science
Datum: 2019-09-15
Språk: eng
Sidantal: 7
Tillhör serie: Bioinformatics
ISSN: 1367-4803
Permanenta länken (URI): http://hdl.handle.net/10138/310638
Abstrakt: 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.
Subject: ORDERED RESTRICTION MAPS
GENOME
ALIGNMENT
SEQUENCE
ALGORITHM
SEARCH
1182 Biochemistry, cell and molecular biology
113 Computer and information sciences
Licens:


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
main_short.pdf 1.353Mb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post