FastSK: fast sequence analysis with gapped string kernels.

Area of Science:

• Bioinformatics
• Computational Biology
• Machine Learning

Background:

• Gapped k-mer kernels with support vector machines (gkm-SVMs) excel at predicting regulatory DNA sequences.
• Existing gkm-SVM algorithms are computationally intensive due to slow kernel computation, limiting their scalability with feature length, mismatches, and alphabet size.

Purpose of the Study:

• Introduce a fast and scalable algorithm for computing gapped k-mer string kernels.
• Improve the efficiency and applicability of gkm-SVMs for sequence analysis tasks.

Main Methods:

• Developed FastSK, a novel algorithm simplifying kernel formulation into independent counting operations.
• Employed a fast Monte Carlo approximation for rapid convergence.
• Applied FastSK to DNA transcription factor binding site prediction, medical named entity recognition, and protein remote homology detection datasets.

Main Results:

• FastSK achieves comparable or superior performance to state-of-the-art gkm-SVMs on DNA binding site prediction.
• Demonstrated significant speedups: ~100x average and ~800x for large feature lengths.
• Outperformed recurrent and convolutional neural networks on DNA sequence tasks with low variance.
• Matched or exceeded baseline performance on medical NER and protein homology detection datasets.

Conclusions:

• FastSK offers a computationally efficient and scalable solution for gapped k-mer kernel calculations.
• The algorithm enhances the practical application of gkm-SVMs across diverse sequence analysis domains.
• FastSK provides a robust alternative to existing methods and deep learning approaches.