A fast weak motif-finding algorithm based on community detection in graphs.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Transcription factor binding site (TFBS) identification is crucial for understanding genetic regulation.
• Existing motif discovery algorithms face challenges with motif diversity, low specificity, and computational constraints.
• The OOPS (one occurrence per sequence) constraint limits the applicability of some state-of-the-art methods.

Purpose of the Study:

• To develop a novel, fast algorithm for identifying long and weak motifs in DNA sequences.
• To address the limitations of existing motif discovery tools, particularly regarding motif length, weakness, and occurrence constraints.
• To enable efficient motif discovery under the ZOMOPS (zero, one or multiple occurrences per sequence) constraint.

Main Methods:

• Introduced TFBSGroup, a heuristic algorithm based on graph community detection.
• Transformed motif search into a dense subgraph discovery problem within a graph.
• Employed a fast community detection method for initial candidate motif identification.
• Utilized greedy refinement to optimize candidate motifs within their respective communities.

Main Results:

• TFBSGroup demonstrates high efficiency, identifying long (e.g., 18, 24 bp) and weak motifs within seconds on synthetic data.
• Successfully identified motifs in a large dataset of prokaryotic promoters from RegulonDB.
• Accurately detected motifs in ChIP-seq data for mouse transcription factors involved in pluripotency.

Conclusions:

• TFBSGroup is a novel heuristic algorithm capable of rapid motif discovery.
• The algorithm effectively identifies long and weak motifs under the ZOMOPS constraint.
• TFBSGroup shows practical utility in real-world biological applications, including promoter and ChIP-seq data analysis.