An Efficient Algorithm for Discovering Motifs in Large DNA Data Sets.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Planted (l,d) motif discovery is crucial for identifying transcription factor binding sites in promoter sequences.
• Next-generation sequencing (NGS) data, like ChIP-seq, presents challenges for motif discovery due to large data volumes.

Purpose of the Study:

• To develop an efficient and effective algorithm for planted (l,d) motif discovery in large NGS datasets.
• To address the limitations of existing methods in handling high-throughput sequencing data.

Main Methods:

• Proposed MCES (Mining and Combining Emerging Substrings), a novel planted (l,d) motif discovery algorithm.
• Implemented a MapReduce-based strategy for distributed mining of emerging substrings to handle large datasets.
• Evaluated MCES on simulated and real ChIP-seq data.

Main Results:

• MCES efficiently and effectively identifies (l,d) motifs in datasets ranging from thousands to millions of sequences.
• MCES demonstrates faster performance compared to state-of-the-art algorithms like F-motif and TraverStringsR.
• MCES accurately identifies motifs with unknown lengths and outperforms CisFinder in accuracy.

Conclusions:

• MCES provides an efficient and accurate solution for planted (l,d) motif discovery in large-scale NGS data.
• The MapReduce-based approach enables distributed processing, enhancing scalability.
• MCES is a valuable tool for analyzing ChIP-seq data to locate transcription factor binding sites.