Related Experiment Videos
Finding exact optimal motifs in matrix representation by partitioning
Henry C M Leung1, Francis Y L Chin
1Department of Computer Science, The University of Hong Kong, Hong Kong. cmleung2@cs.hku.hk
Bioinformatics (Oxford, England)
|October 6, 2005
Summary
This study introduces EOMM, the first algorithm to find exact optimal motifs represented by position-specific scoring matrices (PSSMs). EOMM successfully identifies weak signals missed by other bioinformatics tools.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Identifying common patterns (motifs) in gene promoter regions is crucial for understanding co-expressed genes.
- Position-specific scoring matrices (PSSMs) are a standard method for representing these motifs.
- Existing algorithms struggle to guarantee finding the exact optimal PSSM, especially for longer motifs.
Purpose of the Study:
- To introduce the first algorithm, EOMM, capable of finding the exact optimal matrix-represented motif.
- To address the limitations of current methods in motif discovery.
Main Methods:
- Developed the Exact Optimal Matrix Motif (EOMM) algorithm.
- Employed a branch-and-bound search strategy with recursive partitioning of the solution space.
- The algorithm's accuracy and runtime are adjustable based on desired error bounds.
Main Results:
- EOMM can identify optimal motifs up to size eight or nine exactly.
- For larger motifs, EOMM provides solutions with controllable accuracy.
- Experiments demonstrated EOMM's superior performance in detecting weak signals compared to MEME and MITRA-PSSM on real and simulated data.
Conclusions:
- EOMM represents a significant advancement in exact motif discovery using PSSMs.
- The algorithm offers improved sensitivity for identifying biologically relevant motifs, even with subtle signals.
- EOMM enhances the capabilities of bioinformatics tools for gene regulation analysis.