k-link EST clustering: evaluating error introduced by chimeric sequences under different degrees of linkage

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Expressed sequence tag (EST) clustering is vital for sequence analysis requiring high redundancy.
• Chimeric sequences pose challenges to optimal EST clustering, particularly for single-linkage algorithms.
• Stringent similarity thresholds, used to mitigate chimera effects, reduce clustering sensitivity.

Purpose of the Study:

• Introduce and evaluate k-link clustering for EST data.
• Assess the impact of linkage thresholds on clustering error rates.
• Develop strategies to minimize Type I and Type II errors in EST clustering.

Main Methods:

• Developed the k-link clustering concept for expressed sequence tag data.
• Evaluated clustering error rates across various linkage thresholds.
• Proposed an extension to k-link to adjust link requirements based on cluster size.

Main Results:

• K-link clustering reduces Type II errors as the number of required shared expressed sequence tags (links) increases.
• A baseline Type II error persists, likely due to unmasked low-complexity or repetitive sequences.
• Type I error increases with higher linkage requirements, addressed by the proposed k-link extension.

Conclusions:

• K-link clustering offers a robust approach to handle expressed sequence tag data.
• The k-link extension effectively balances error rates by adapting linkage requirements.
• This method enhances the accuracy and sensitivity of EST sequence analysis.