CFSP: a collaborative frequent sequence pattern discovery algorithm for nucleic acid sequence classification.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Conserved nucleic acid sequences are vital for transcriptional regulation and serve as biomarkers.
• Motif extraction from large-scale data is crucial for developing predictive models.
• Template-based classification often outperforms feature extraction methods like N-gram.

Purpose of the Study:

• To propose a novel feature extraction algorithm for discovering frequent subsequences in nucleic acid data.
• To improve motif discovery by capturing long-distance correlations and handling sequence variations.
• To enhance the creation of predictive models for biochemical properties and non-coding RNAs.

Main Methods:

• Introduced a Teiresias-like algorithm called CFSP (Common Frequent Sub-sequence Pattern) for motif discovery.
• CFSP allows for larger gaps in sequence pairs compared to existing algorithms.
• Incorporated mutation information for fuzzy matching to accommodate single nucleotide variants and indels.

Main Results:

• The CFSP algorithm successfully identified frequent subsequence combinations, capturing long-distance correlations.
• Validated the algorithm with case studies involving miRNA, piRNA, and Sigma 54 promoters.
• Demonstrated superior performance compared to existing feature descriptor-based methods.

Conclusions:

• The proposed CFSP algorithm is effective for nucleic acid sequence prediction.
• CFSP offers improved motif extraction capabilities, outperforming current methods.
• The algorithm is publicly available in C++ and shell script.