SamSelect: a sample sequence selection algorithm for quorum planted motif search on large DNA datasets.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Quorum planted motif search (qPMS) identifies DNA motifs, crucial for locating transcription factor binding sites.
• Existing qPMS algorithms struggle with large datasets like ChIP-seq, requiring excessive computation time.

Purpose of the Study:

• To improve the efficiency of qPMS algorithms for large-scale DNA datasets.
• To reduce the computational time required for motif discovery.

Main Methods:

• Analyzed the impact of dataset size (t) and quorum threshold (q) on qPMS performance.
• Developed a sample sequence selection algorithm (SamSelect) to create a smaller, representative dataset (D') with optimal parameters (small t, large q).
• Executed qPMS algorithms on the selected subset (D') instead of the entire dataset (D).

Main Results:

• SamSelect efficiently selects high-quality sample sequence sets (D').
• qPMS algorithms run significantly faster on the selected subset (D') compared to the original dataset (D).
• The method effectively finds planted or real motifs in large DNA datasets.

Conclusions:

• The proposed method enhances the scalability of qPMS algorithms for large DNA datasets.
• By using high-quality sample sets, motif discovery can be performed in a significantly shorter time.
• This approach offers an approximate yet efficient solution for motif discovery in genomics.