Related Experiment Videos
Parallel sequence alignment in limited space
Proceedings. International Conference on Intelligent Systems for Molecular Biology
|January 1, 1995
Summary
This study presents new algorithms for sequence alignment on parallel processors. These methods reduce memory requirements for single-instruction, multiple-data (SIMD) systems, enabling efficient alignment computation.
Area of Science:
- Bioinformatics
- Computational Biology
- Algorithm Design
Background:
- Sequence comparison is parallelizable on SIMD processors.
- Sequence alignment, however, is more complex and not suitable for SIMD with local communication.
Purpose of the Study:
- To propose methods for computing sequence alignments on SIMD processors with limited memory.
- To develop algorithms suitable for both parallel and serial implementations.
Main Methods:
- Developed algorithms that reduce space complexity from O(n) to O(L sqrt(n)) per processing element.
- Introduced a trade-off between slowdown (factor of L) and space requirements.
- Designed an O(n log n) parallel time algorithm using O(log n) space per SIMD processing element.
Main Results:
- Achieved efficient sequence alignment computation on SIMD architectures.
- Algorithms are adaptable for serial processing.
- Demonstrated an O(n log n) parallel time complexity with reduced space overhead.
Conclusions:
- The proposed methods enable efficient sequence alignment on hardware-constrained SIMD systems.
- These algorithms offer a practical solution for large-scale sequence analysis.
- The work bridges the gap between theoretical algorithms and practical hardware implementations.