FastSK

FastSK computes gapped k-mer string kernels to perform fast, scalable sequence analysis for tasks such as regulatory DNA transcription factor binding prediction and protein sequence classification.

Key Features:

• Algorithmic Innovation: Decomposes gapped k-mer kernel computation into independent counting operations over possible mismatch positions.
• Monte Carlo Approximation: Employs a fast Monte Carlo approximation that rapidly converges, enabling handling of larger feature lengths and more mismatches.
• Scalability and Performance: Achieves average kernel computation speedups of approximately 100× and up to 800× for large feature lengths compared to gkm-SVM-2.0.
• Predictive Accuracy: Matches or surpasses gkm-SVM-2.0 in area under the ROC curve for DNA transcription factor binding site datasets and outperforms character-level recurrent and convolutional neural networks while maintaining low variance.

Scientific Applications:

• DNA Sequence Analysis: Predicting transcription factor binding sites in regulatory DNA sequences.
• Medical Named Entity Recognition: Applied to seven English-language medical named entity recognition datasets, matching or outperforming existing baselines.
• Protein Remote Homology Detection: Evaluated on ten protein remote homology detection datasets with strong performance.

Methodology:

Computes gapped k-mer string kernels by decomposing kernel calculations into independent counting over mismatch positions and applies a fast Monte Carlo approximation for kernel estimation.