Tsukuba BB: a branch and bound algorithm for local multiple alignment of DNA and protein sequences

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Development

Background:

• Multiple sequence alignment is crucial for understanding biological sequences.
• Existing algorithms struggle with scalability and computational complexity for motif discovery.
• Local gapless multiple sequence alignment (motif alignment) presents unique computational challenges.

Purpose of the Study:

• To present a novel branch and bound algorithm for local gapless multiple sequence alignment.
• To implement an efficient algorithm that exploits problem characteristics for faster motif discovery.
• To demonstrate the algorithm's superior performance on biological datasets.

Main Methods:

• Developed a branch and bound algorithm incorporating score-based and consistency-based bounding techniques.
• Utilized a sequence order independent search tree with redundancy avoidance.
• Exploited the property that motif alignment is easier for shorter motifs, achieving linear time complexity.
• Introduced an alphabet size reduction technique for protein sequence datasets.

Main Results:

• The algorithm achieves asymptotically linear running time for short, fixed motif widths.
• Successfully aligned entire sets of sequences for motif width 4.
• Aligned 21 sequences (length 100) for motif width 6, outperforming previous exact algorithms by over twofold.
• Aligned 105 out of 300 promoter sequences with motif width 6 when relaxing alignment constraints.
• Demonstrated efficient motif discovery on lipocalin protein sequences using alphabet reduction.

Conclusions:

• The developed algorithm offers a significant advancement in motif alignment efficiency and scalability.
• It enables the analysis of larger biological sequence datasets than previously possible.
• The approach provides a powerful tool for discovering meaningful motifs in genomics and proteomics.