Related Experiment Videos
Pattern matching of biological sequences with limited storage
1Department of Biochemistry, Saitama Cancer Center Research Institute, Japan.
Computer Applications in the Biosciences : CABIOS
|March 1, 1987
Summary
This study introduces an efficient algorithm for biological sequence alignment, significantly reducing memory needs while maintaining optimal local alignment accuracy. The method aids in identifying common subsequences with high similarity scores.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Traditional sequence alignment methods require substantial computational resources (O(N^2) time and space).
- Efficiently identifying locally optimal alignments and common subsequences is crucial for biological data analysis.
Purpose of the Study:
- To develop an improved algorithm for locally best matched sequence alignment.
- To reduce the storage requirements of sequence alignment while maintaining computational efficiency.
- To facilitate the identification of common subsequences exceeding a specified similarity threshold.
Main Methods:
- An algorithm was developed to achieve locally maximal alignments.
- The method optimizes storage, reducing it significantly compared to existing O(N^2) approaches.
- Implementation in C allows for efficient execution on personal computers.
Main Results:
- The algorithm achieves O(N^2) computational steps with greatly reduced storage needs.
- Minimal additional steps are required to display common subsequences above a similarity threshold.
- A 64 kbyte RAM and few hundred kbyte disk space suffice for comparing long sequences (2500 residues).
Conclusions:
- The presented algorithm offers a memory-efficient solution for locally optimal biological sequence alignment.
- This method enhances the utility of sequence alignment tools, especially when combined with fast search programs.
- The optimized approach is valuable for analyzing large biological sequence datasets on standard hardware.