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
We undertake a critical appraisal of the existence of the so- called 'sweet spot' in ethical trade at which the interests of buyers, suppliers, and workers intersect to enable benefits for commercial buyers and suppliers ...
Van der Merwe, Theo(University of Pretoria, 2006-08-03)
The dissertation "Alignment of supply and demand within a supply chain: a qualitative study” determines the causes of the misalignment between the supply and demand within a supply chain, with specific focus on Kraft Foods ...
Oosthuizen, William Thomas(University of Pretoria, 2014)
The South African health system faces numerous challenges. A
large majority of the population are dependent and have to
contend with a dysfunctional public sector. The quality of
care patients receive is severely ...