Bit-parallel sequence-to-graph alignment

Näytä kaikki kuvailutiedot



Pysyväisosoite

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

Lähdeviite

Rautiainen , M , Mäkinen , V & Marschall , T 2019 , ' Bit-parallel sequence-to-graph alignment ' , Bioinformatics , vol. 35 , no. 19 , pp. 3599-3607 . https://doi.org/10.1093/bioinformatics/btz162

Julkaisun nimi: Bit-parallel sequence-to-graph alignment
Tekijä: Rautiainen, Mikko; Mäkinen, Veli; Marschall, Tobias
Muu tekijä: University of Helsinki, Genome-scale Algorithmics research group / Veli Mäkinen
Päiväys: 2019-10-01
Kieli: eng
Sivumäärä: 9
Kuuluu julkaisusarjaan: Bioinformatics
ISSN: 1367-4803
URI: http://hdl.handle.net/10138/308160
Tiivistelmä: Motivation: Graphs are commonly used to represent sets of sequences. Either edges or nodes can be labeled by sequences, so that each path in the graph spells a concatenated sequence. Examples include graphs to represent genome assemblies, such as string graphs and de Bruijn graphs, and graphs to represent a pan-genome and hence the genetic variation present in a population. Being able to align sequencing reads to such graphs is a key step for many analyses and its applications include genome assembly, read error correction and variant calling with respect to a variation graph. Results: We generalize two linear sequence-to-sequence algorithms to graphs: the Shift-And algorithm for exact matching and Myers' bitvector algorithm for semi-global alignment. These linear algorithms are both based on processing w sequence characters with a constant number of operations, where w is the word size of the machine (commonly 64), and achieve a speedup of up to w over naive algorithms. For a graph with vertical bar V vertical bar nodes and vertical bar E vertical bar edges and a sequence of length m, our bitvector-based graph alignment algorithm reaches a worst case runtime of O(vertical bar V vertical bar+(sic)m/w(sic)vertical bar E vertical bar logw) for acyclic graphs and O(vertical bar V vertical bar+m vertical bar E vertical bar logw) for arbitrary cyclic graphs. We apply it to five different types of graphs and observe a speedup between 3-fold and 20-fold compared with a previous (asymptotically optimal) alignment algorithm.
Avainsanat: DE-BRUIJN GRAPHS
APPROXIMATE
ALGORITHM
ACCURATE
1182 Biochemistry, cell and molecular biology
113 Computer and information sciences
111 Mathematics
Tekijänoikeustiedot:


Tiedostot

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

Tiedosto(t) Koko Formaatti Näytä
btz162.pdf 977.7KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot