MoDEL: an efficient strategy for ungapped local multiple alignment.
We introduce a method for ungapped local multiple alignment (ULMA) in a given set of amino acid or nucleotide sequences. This method explores two search spaces using a linked optimization strategy. The first search space M consists of all possible words of a given length W, defined on the residue alphabet. An evolutionary algorithm searches this space globally. The second search space P consists of all possible ULMAs in the sequence set, each ULMA being represented by a position vector defining exactly one subsequence of length W per sequence. This search space is sampled with hill-climbing processes. The search of both spaces are coupled by projecting high scoring results from the global evolutionary search of M onto P. The hill-climbing processes then refine the optimization by local search, using the relative entropy between the ULMA and background residue frequencies as an objective function. We demonstrate some advantages of our strategy by analyzing difficult natural amino acid sequences and artificial datasets. A web interface is available at
Hernandez
David
D
Proteome Informatics Group, Swiss Institute of Bioinformatics, CMU, 1 rue Michel-Servet, CH 1211 Geneva 4, Switzerland. david.hernandez@isb-sib.ch
Gras
Robin
R
Appel
Ron
R
D000465:Algorithms; D000595:Amino Acid Sequence / Q000235:genetics*; D001483:Base Sequence / Q000235:genetics*; D016208:Databases, Factual; D019077:Helix-Turn-Helix Motifs; D008969:Molecular Sequence Data; D016415:Sequence Alignment / Q000379:methods*; D012984:Software; D013997:Time Factors