Journal Article

HIGEDA: a hierarchical gene-set genetics based algorithm for finding subtle motifs in biological sequences

Thanh Le, Tom Altman and Katheleen Gardiner

in Bioinformatics

Volume 26, issue 3, pages 302-309
Published in print February 2010 | ISSN: 1367-4803
Published online December 2009 | e-ISSN: 1460-2059 | DOI:
HIGEDA: a hierarchical gene-set genetics based algorithm for finding subtle motifs in biological sequences

More Like This

Show all results sharing this subject:

  • Bioinformatics and Computational Biology


Show Summary Details


Motivation: Identification of motifs in biological sequences is a challenging problem because such motifs are often short, degenerate, and may contain gaps. Most algorithms that have been developed for motif-finding use the expectation-maximization (EM) algorithm iteratively. Although EM algorithms can converge quickly, they depend strongly on initialization parameters and can converge to local sub-optimal solutions. In addition, they cannot generate gapped motifs. The effectiveness of EM algorithms in motif finding can be improved by incorporating methods that choose different sets of initial parameters to enable escape from local optima, and that allow gapped alignments within motif models.

Results: We have developed HIGEDA, an algorithm that uses the hierarchical gene-set genetic algorithm (HGA) with EM to initiate and search for the best parameters for the motif model. In addition, HIGEDA can identify gapped motifs using a position weight matrix and dynamic programming to generate an optimal gapped alignment of the motif model with sequences from the dataset. We show that HIGEDA outperforms MEME and other motif-finding algorithms on both DNA and protein sequences.

Availability and implementation: Source code and test datasets are available for download at∼tnle/, implemented in C++ and supported on Linux and MS Windows.


Journal Article.  5386 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.