Related Experiment Video
Updated: Jul 10, 2026
07:08
Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
Published on: July 14, 2015
Fast and practical algorithms for planted (l, d) motif search.
Jaime Davila1, Sudha Balla, Sanguthevar Rajasekaran
1Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269-3155, USA. jdavila@engr.uconn.edu
IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 3, 2007
Summary
We developed new algorithms to find DNA motifs with errors, improving the search for transcription factor-binding sites. Our PMSprune algorithm solves previously unsolvable complex instances, advancing genomic analysis.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- The planted (l, d) motif search problem is crucial for identifying transcription factor-binding sites in genomic sequences.
- Existing methods face challenges with larger error tolerances (d) and longer motifs (l).
Purpose of the Study:
- To propose a series of practical, exact algorithms for the (l, d) motif search problem.
- To improve efficiency and handle more challenging instances than previously possible.
Main Methods:
- Algorithms based on the PMS1 approach were developed.
- Focus on exact solutions with minimal space requirements.
- Implementation and testing of a specific algorithm, PMSprune.
Main Results:
- The proposed algorithms efficiently solve challenging (l, d) motif search instances.
- PMSprune successfully solved instances like (17, 6) and (19, 7), which were previously unsolved.
- Algorithms demonstrate reduced computation time for solvable instances.
Conclusions:
- The developed algorithms offer significant improvements for the (l, d) motif search problem.
- PMSprune represents a breakthrough in solving complex motif discovery tasks in genomics.
- These advancements facilitate more accurate identification of functional elements in DNA.
Related Concept Videos
01:24DNA Isolation
DNA isolation protocols can be fast and straightforward or complex and time-consuming depending on the type and quality of DNA required for further processing. For example, plasmid DNA extraction is a bit more complicated than genomic DNA extraction because of the need for an appropriate lysis method to separate plasmid DNA from gDNA during isolation. However, for specific applications, such as long-range DNA sequencing that require a good yield of high- quality DNA samples, we need to follow...
02:54Evolutionary Relationships through Genome Comparisons
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...