Fast sequence clustering using a suffix array algorithm.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Efficient clustering of expressed sequence tag (EST) data is crucial for managing large biological sequence datasets.
• Current clustering methods often rely on all-against-all comparisons, leading to quadratic time complexity that hinders scalability.
• The rapid growth of EST data necessitates novel, more efficient computational approaches.

Purpose of the Study:

• To introduce a novel, fast algorithm for clustering expressed sequence tag (EST) data.
• To address the limitations of existing quadratic time complexity methods in handling large EST datasets.
• To provide a scalable solution for EST data analysis.

Main Methods:

• Development of a new EST clustering algorithm utilizing suffix arrays.
• Achieving sub-quadratic time complexity through the suffix array-based approach.
• Implementation of a prototype for the developed algorithm.

Main Results:

• The prototype implementation demonstrated promising results on a benchmark dataset.
• Clusterings generated by the new algorithm were validated against existing methods.
• The suffix array approach successfully reduced computational time complexity.

Conclusions:

• The presented algorithm offers an efficient and scalable solution for EST clustering.
• This method is well-suited for analyzing the ever-increasing volume of EST data.
• The source code is publicly available, promoting further research and application.