Search: WFRF:(Norberg Peter 1974)
> (2020-2021) >
Fast parallel const...
Fast parallel construction of variable-length Markov chains
-
- Gustafsson, Joel (author)
- Gothenburg University,Göteborgs universitet,Institutionen för biomedicin, avdelningen för infektionssjukdomar,Institute of Biomedicine, Department of Infectious Medicine
-
- Norberg, Peter, 1974 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för biomedicin, avdelningen för infektionssjukdomar,Institute of Biomedicine, Department of Infectious Medicine
-
- Qvick-Wester, Jan R. (author)
- Gothenburg University,Göteborgs universitet,Institutionen för data- och informationsteknik, datavetenskap (GU),Department of Computer Science and Engineering, Computing Science (GU)
-
show more...
-
- Schliep, Alexander, 1967 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för data- och informationsteknik (GU),Department of Computer Science and Engineering (GU)
-
show less...
-
(creator_code:org_t)
- 2021-10-09
- 2021
- English.
-
In: Bmc Bioinformatics. - : Springer Science and Business Media LLC. - 1471-2105. ; 22:1
- Related links:
-
https://bmcbioinform...
-
show more...
-
https://gup.ub.gu.se...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- Background: Alignment-free methods are a popular approach for comparing biological sequences, including complete genomes. The methods range from probability distributions of sequence composition to first and higher-order Markov chains, where a k-th order Markov chain over DNA has 4k formal parameters. To circumvent this exponential growth in parameters, variable-length Markov chains (VLMCs) have gained popularity for applications in molecular biology and other areas. VLMCs adapt the depth depending on sequence context and thus curtail excesses in the number of parameters. The scarcity of available fast, or even parallel software tools, prompted the development of a parallel implementation using lazy suffix trees and a hash-based alternative. Results: An extensive evaluation was performed on genomes ranging from 12Mbp to 22Gbp. Relevant learning parameters were chosen guided by the Bayesian Information Criterion (BIC) to avoid over-fitting. Our implementation greatly improves upon the state-of-the-art even in serial execution. It exhibits very good parallel scaling with speed-ups for long sequences close to the optimum indicated by Amdahl's law of 3 for 4 threads and about 6 for 16 threads, respectively. Conclusions: Our parallel implementation released as open-source under the GPLv3 license provides a practically useful alternative to the state-of-the-art which allows the construction of VLMCs even for very large genomes significantly faster than previously possible. Additionally, our parameter selection based on BIC gives guidance to endusers comparing genomes.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Bioinformatik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Bioinformatics (hsv//eng)
Keyword
- Variable-length Markov chain
- Sequence analysis
- Parallel algorithms
- Alignment-free
- probabilistic-automata
- prediction
- alignment
- Biochemistry & Molecular Biology
- Biotechnology & Applied Microbiology
- Mathematical & Computational Biology
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database