A graph-theoretical approach for motif discovery in protein sequences

Area of Science:

• Bioinformatics
• Computational Biology
• Graph Theory

Background:

• Protein motif recognition is complex due to motif diversity.
• Existing algorithms struggle with variable-length and gapped motifs.
• Current methods are computationally intensive, especially for gapped motifs.

Purpose of the Study:

• To develop a novel graph theoretical approach for identifying protein motifs of various lengths, including gapped motifs.
• To compare the new method's performance against established algorithms like MEME and GLAM2.
• To improve the efficiency and accuracy of motif discovery in bioinformatics.

Main Methods:

• A new graph theoretical approach was developed to identify motifs with variable lengths and gaps.
• The method was compared with MEME and GLAM2 using quality of results and computational time metrics.
• Similarity indexing was employed to further optimize query times.

Main Results:

• The novel method achieved slightly higher quality results than MEME, with significantly reduced computational time (one-eighth of MEME's).
• Compared to GLAM2, the new approach demonstrated a sixfold reduction in query times while maintaining slightly superior result quality.
• The method is particularly efficient for smaller sequence collections, outperforming GLAM2 significantly.

Conclusions:

• The proposed graph theoretical approach offers an efficient and accurate solution for identifying variable-length and gapped protein motifs.
• This method presents a significant advancement over existing tools, offering a better balance of speed and accuracy.
• The freely available C++ implementation facilitates broader adoption and further research in motif discovery.