Related Experiment Video
Updated: Jun 17, 2026
08:03
Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
HIGEDA: a hierarchical gene-set genetics based algorithm for finding subtle motifs in biological sequences.
Thanh Le1, Tom Altman, Katheleen Gardiner
1Department of Computer Science and Engineering, Computational Biosciences Program, University of Colorado, Denver, CO, USA.
Bioinformatics (Oxford, England)
|December 10, 2009
Summary
HIGEDA, a novel algorithm, enhances motif discovery in biological sequences by combining a hierarchical gene-set genetic algorithm with expectation-maximization. This approach effectively identifies gapped motifs, outperforming existing methods in DNA and protein sequence analysis.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Motif identification in biological sequences is complex due to short, degenerate, and gapped patterns.
- Traditional expectation-maximization (EM) algorithms for motif finding can converge to local optima and struggle with gapped motifs.
Purpose of the Study:
- To develop an improved algorithm for motif discovery that overcomes limitations of existing methods.
- To enable the identification of gapped motifs in biological sequences.
Main Methods:
- Developed HIGEDA, integrating a hierarchical gene-set genetic algorithm (HGA) with EM for parameter optimization.
- Utilized position weight matrices and dynamic programming for optimal gapped alignment generation.
Main Results:
- HIGEDA successfully identifies gapped motifs in both DNA and protein sequences.
- The HIGEDA algorithm demonstrates superior performance compared to MEME and other established motif-finding tools.
Conclusions:
- HIGEDA offers a robust and effective solution for motif discovery, particularly for gapped motifs.
- The algorithm's ability to escape local optima and handle gapped alignments enhances its utility in bioinformatics.
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: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...
01:11Genome-wide Association Studies-GWAS
Genome-wide association studies or GWAS are used to identify whether common SNPs are associated with certain diseases. Suppose specific SNPs are more frequently observed in individuals with a particular disease than those without the disease. In that case, those SNPs are said to be associated with the disease. Chi-square analysis is performed to check the probability of the allele likely to be associated with the disease.
GWAS does not require the identification of the target gene involved in...
GWAS does not require the identification of the target gene involved in...
02:51Multi-species Conserved Sequences
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
02:02Cis-regulatory Sequences
Cis-regulatory sequences are short fragments of non-coding DNA that are present on the same chromosomes as the genes that they regulate. These fragments serve as binding sites for transcriptional regulators, proteins that are responsible for controlling gene transcription and differential gene expression across cell types in eukaryotes. Cis-regulatory sequences can be close to the gene of interest or thousands of bases away in the DNA sequence; however, those sequences that are further away are...
02:02Cis-regulatory Sequences
Cis-regulatory sequences are short fragments of non-coding DNA that are present on the same chromosomes as the genes that they regulate. These fragments serve as binding sites for transcriptional regulators, proteins that are responsible for controlling gene transcription and differential gene expression across cell types in eukaryotes. Cis-regulatory sequences can be close to the gene of interest or thousands of bases away in the DNA sequence; however, those sequences that are further away are...