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. The source code is
available at: https://github.com/biointec/browniealigner
Additional file 1: Supplementary Data: BrownieAligner: Accurate
Alignment of Illumina Sequencing Data to de Bruijn Graphs
Road safety education is a complex phenomenon which should be viewed holistically if taken into account the interconnectedness of education, infrastructure and enforcement. Effective road safety education is specifically ...
Sustainable development depends on coherence between the development policies of recipients and the providers of development assistance. Yet achieving coherence is difficult. This paper examines the extent to which the ...
Blyth, David Holborn(University of Pretoria, 2003-06-19)
The key mission of a defence force is the ability to execute successful operations. If it is unable to do this, it is only a liability to the nation, and its right to exist ceases. The White Paper on defence requires the ...