Advanced search
1 file | 835.97 KB

BrownieAligner : accurate alignment of Illumina sequencing data to de Bruijn graphs

Mahdi Heydari (UGent) , Giles Miclotte (UGent) , Yves Van de Peer (UGent) and Jan Fostier (UGent)
Author
Organization
Abstract
Background: Aligning short reads to a reference genome is an important task in many genome analysis pipelines. This task is computationally more complex when the reference genome is provided in the form of a de Bruijn graph instead of a linear sequence string. Results: We present a branch and bound alignment algorithm that uses the seed-and-extend paradigm to accurately align short Illumina reads to a graph. Given a seed, the algorithm greedily explores all branches of the tree until the optimal alignment path is found. To reduce the search space we compute upper bounds to the alignment score for each branch and discard the branch if it cannot improve the best solution found so far. Additionally, by using a two-pass alignment strategy and a higher-order Markov model, paths in the de Bruijn graph that do not represent a subsequence in the original reference genome are discarded from the search procedure. Conclusions: BrownieAligner is applied to both synthetic and real datasets. It generally outperforms other state-of-the-art tools in terms of accuracy, while having similar runtime and memory requirements. Our results show that using the higher-order Markov model in BrownieAligner improves the accuracy, while the branch and bound algorithm reduces runtime. BrownieAligner is written in standard C++11 and released under GPL license. BrownieAligner relies on multithreading to take advantage of multi-core/multi-CPU systems.
Keywords
Next-generation sequencing, Graph alignment, Illumina, de Bruijn Graph, Markov Model, READ ALIGNMENT, GENOME

Downloads

  • s12859-018-2319-7.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 835.97 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Heydari, Mahdi, Giles Miclotte, Yves Van de Peer, and Jan Fostier. 2018. “BrownieAligner : Accurate Alignment of Illumina Sequencing Data to De Bruijn Graphs.” Bmc Bioinformatics 19.
APA
Heydari, M., Miclotte, G., Van de Peer, Y., & Fostier, J. (2018). BrownieAligner : accurate alignment of Illumina sequencing data to de Bruijn graphs. BMC BIOINFORMATICS, 19.
Vancouver
1.
Heydari M, Miclotte G, Van de Peer Y, Fostier J. BrownieAligner : accurate alignment of Illumina sequencing data to de Bruijn graphs. BMC BIOINFORMATICS. 2018;19.
MLA
Heydari, Mahdi, Giles Miclotte, Yves Van de Peer, et al. “BrownieAligner : Accurate Alignment of Illumina Sequencing Data to De Bruijn Graphs.” BMC BIOINFORMATICS 19 (2018): n. pag. Print.
@article{8573910,
  abstract     = {Background: Aligning short reads to a reference genome is an important task in many genome analysis pipelines. This task is computationally more complex when the reference genome is provided in the form of a de Bruijn graph instead of a linear sequence string. 
Results: We present a branch and bound alignment algorithm that uses the seed-and-extend paradigm to accurately align short Illumina reads to a graph. Given a seed, the algorithm greedily explores all branches of the tree until the optimal alignment path is found. To reduce the search space we compute upper bounds to the alignment score for each branch and discard the branch if it cannot improve the best solution found so far. Additionally, by using a two-pass alignment strategy and a higher-order Markov model, paths in the de Bruijn graph that do not represent a subsequence in the original reference genome are discarded from the search procedure. 
Conclusions: BrownieAligner is applied to both synthetic and real datasets. It generally outperforms other state-of-the-art tools in terms of accuracy, while having similar runtime and memory requirements. Our results show that using the higher-order Markov model in BrownieAligner improves the accuracy, while the branch and bound algorithm reduces runtime. BrownieAligner is written in standard C++11 and released under GPL license. BrownieAligner relies on multithreading to take advantage of multi-core/multi-CPU systems.},
  articleno    = {311},
  author       = {Heydari, Mahdi and Miclotte, Giles and Van de Peer, Yves and Fostier, Jan},
  issn         = {1471-2105},
  journal      = {BMC BIOINFORMATICS},
  keyword      = {Next-generation sequencing,Graph alignment,Illumina,de Bruijn Graph,Markov Model,READ ALIGNMENT,GENOME},
  language     = {eng},
  pages        = {10},
  title        = {BrownieAligner : accurate alignment of Illumina sequencing data to de Bruijn graphs},
  url          = {http://dx.doi.org/10.1186/s12859-018-2319-7},
  volume       = {19},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: