Accelerating approximate subsequence search on large protein sequence databases

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• The volume of biological sequence data is rapidly increasing.
• Current sequence retrieval tools like BLAST are computationally intensive for large databases.
• Existing indexing methods, such as suffix trees, face memory limitations with large protein sequence datasets.

Purpose of the Study:

• To develop an efficient indexing structure for large protein sequence databases.
• To enable sublinear time approximate sequence matching.
• To overcome the limitations of existing methods like BLAST and suffix trees.

Main Methods:

• Implementation of the BASS-tree indexing structure for protein sequences.
• Development of the sequence approximate match (SAM) index method.
• Experimental evaluation of the SAM index method against BLAST and suffix trees.

Main Results:

• The BASS-tree based SAM index method achieves sublinear time complexity for approximate matching.
• Experimental results show an order of magnitude performance improvement over BLAST and suffix trees.
• The proposed method effectively directs searches to relevant database portions for faster matching.

Conclusions:

• The BASS-tree offers a scalable and efficient solution for indexing large protein sequence databases.
• The SAM index method significantly enhances the speed of approximate sequence matching.
• This approach provides a valuable tool for bioinformatics research dealing with massive sequence data.