Set cover-based methods for motif selection.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• De novo motif discovery algorithms identify transcription factor binding sites but often yield too many motifs.
• The motif selection problem aims to find a minimal set of motifs for sequences of interest, like ChIP-Seq regions.

Purpose of the Study:

• To address the motif selection problem by mapping it to variants of the set cover problem.
• To develop and evaluate new algorithms for identifying high-quality, minimal sets of regulatory motifs.

Main Methods:

• The motif selection problem was modeled as set cover problems.
• Tabu search and relaxed integer linear programming (RILP) were employed to solve these problems.
• Algorithms were applied to 349 ChIP-Seq experiments from the ENCODE project.

Main Results:

• Set cover-based algorithms identified a small number of high-quality motifs representing putative transcription factor binding sites.
• Compared to existing methods, algorithms improved peak coverage by 35% for 11 TFs and identified 4 additional cofactors for 6 TFs.
• The RILP algorithm showed superior performance, selecting fewer motifs, covering more peaks (6%), and reducing the error rate by 7%.

Conclusions:

• Novel set cover algorithms effectively solve the motif selection problem.
• These methods provide a more efficient and accurate approach for identifying regulatory motifs from large-scale genomic data.
• The developed tools and datasets are publicly available for further research.