Related Experiment Video
Updated: Jun 25, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
DNA motif alignment by evolving a population of Markov chains
1Bioinformatics and Intelligent Computing Lab, Division of Clinical Pharmacology, Children's Mercy Hospitals, Kansas City, Missouri, USA. cbi@cmh.edu
BMC Bioinformatics
|February 12, 2009
Summary
This study introduces a novel algorithm for de novo motif-finding in genomes. By enabling information exchange between Markov chains, the new method improves convergence and outperforms existing algorithms for identifying cis-regulatory elements.
Area of Science:
- Genomics
- Bioinformatics
- Computational Biology
Background:
- De novo motif-finding in genomes is challenging, with existing Markov chain Monte Carlo (MCMC) methods like Gibbs samplers often getting stuck in local maxima.
- Current MCMC approaches require multiple independent runs without information exchange, limiting their efficiency in finding optimal local alignments.
Purpose of the Study:
- To develop a novel motif-finding algorithm that overcomes the limitations of existing methods by enabling information exchange between computational processes.
- To improve the accuracy and efficiency of identifying cis-regulatory elements and de novo motifs in genomic sequences.
Main Methods:
- Introduced a population-based motif-finding algorithm using information exchange (PMC) that evolves a population of Markov chains.
- Employed the Metropolis-Hastings sampler (MHS) and a population-based proposal distribution for stochastic sampling and adaptive evolution towards a global maximum.
- Developed an independent Markov chains (IMC) algorithm for comparison, running multiple chains without information exchange.
Main Results:
- Experimental studies confirmed that pooling information among motif samplers enhances performance.
- The novel PMC algorithm demonstrated improved convergence rates compared to traditional methods.
- The PMC algorithm outperformed other popular motif-finding algorithms on both simulated and biological motif sequences.
Conclusions:
- Utilizing pooled information in a population of motif samplers significantly improves performance in de novo motif-finding.
- The developed PMC algorithm offers a more effective and convergent approach for identifying genomic motifs compared to existing methods.
Related Concept Videos
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...
01:49Conserved Binding Sites
Many proteins’ biological role depends on their interactions with their ligands, small molecules that bind to specific locations on the protein known as ligand-binding sites. Ligand-binding sites are often conserved among homologous proteins as these sites are critical for protein function.
Binding sites are often located in large pockets, and if their location on a protein’s surface is unknown, it can be predicted using various approaches. The energetic method computationally analyses the...
Binding sites are often located in large pockets, and if their location on a protein’s surface is unknown, it can be predicted using various approaches. The energetic method computationally analyses the...
02:26Conservation of Protein Domains Over Different Proteins
Protein domains are small structurally independent units that are part of a single amino acid chain. Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
02:26Conservation of Protein Domains
Protein domains are small structurally independent units that are part of a single amino acid chain. Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
01:29Modern Molecular Taxonomy
Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...
02:05Gene Evolution - Fast or Slow?
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...