Reduced space sequence alignment

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithm Design

Background:

• Sequence alignment is fundamental in bioinformatics for comparing biological sequences.
• Standard algorithms require substantial memory (O(n^2)) or are limited in parallelization.
• Hirschberg's algorithm reduces space but can be slow.

Purpose of the Study:

• To develop novel sequence alignment methods with reduced memory footprints.
• To create algorithms suitable for both serial and parallel computing environments.
• To enable efficient training of linear hidden Markov models.

Main Methods:

• A family of algorithms is presented for sequence alignment with reduced memory.
• These methods achieve space complexity of O(n^1.5) with a tunable slowdown factor (L).
• A specific algorithm matches Hirschberg's space-time complexity but offers practical speedups.

Main Results:

• The proposed algorithms reduce memory requirements from O(n^2) to O(n^1.5).
• They are well-suited for parallel implementation and avoid data-dependent repartitioning.
• The O(n^1.5)-space algorithm demonstrates a 15-40% speed improvement over Hirschberg's method.

Conclusions:

• This work introduces memory-efficient sequence alignment algorithms.
• The new methods provide a trade-off between space reduction and computational time.
• These algorithms enhance the feasibility of large-scale sequence analysis and model training.