k-link

k-link enhances clustering of expressed sequence tags (ESTs) by applying a variable-linkage merging strategy to reduce erroneous cluster merges caused by chimeric sequences.

Key Features:

• Variable Linkage Thresholds: Varies the number of shared ESTs (links) required for merging clusters to adjust clustering sensitivity and specificity.
• Error Rate Optimization: Evaluates Type I (false positive) and Type II (false negative) error rates across different linkage thresholds and reports that increasing required links reduces Type II errors caused by unmasked low-complexity or repetitive sequences.
• Cluster-size-based Link Adjustment: Adjusts the required number of shared links based on the sizes of clusters being compared to balance Type I and Type II errors.
• Chimera Robustness: Mitigates the impact of chimeric sequences that can produce incorrect merges in single-linkage clustering.
• Implementation: Implemented in C++.

Scientific Applications:

• EST clustering in genomic studies: Improves precise identification and grouping of ESTs in genomic analyses with high sequence redundancy.
• High-throughput sequencing projects: Applicable to high-throughput projects that require robust handling of chimeric sequences and redundant reads.
• Robust sequence analysis: Suitable for workflows needing mitigation of effects from chimeras, low-complexity regions, or repetitive sequences.

Methodology:

Uses a variable-linkage merging strategy that varies the number of shared ESTs required to merge clusters, evaluates Type I and Type II error rates across linkage thresholds, and includes an extension that adjusts required links based on cluster sizes; implemented in C++.