Neighborhood functions and hill-climbing strategies dedicated to the generalized ungapped local multiple alignment

作者：Hernandez David^*; Gras Robin; Appel Ron

来源：European Journal of Operational Research, 2008, 185(3): 1276-1284.

DOI：10.1016/j.ejor.2005.10.076

• local multiple alignment
• motif discovery

Ungapped Local Multiple Alignment is a widely used procedure in bioinformatics. It roughly consists of locating in a given set of nucleotide (DNA) or amino acid (proteins) sequences, a number of non-overlapping fixed-size factors (also called occurrences), that are likely to have evolved from a common ancestor. In addition to the widely known statistical approaches, we define the problem from a pure combinatorial optimization point of view, by defining specific neighborhood functions and a hill-climbing strategy for each of four particular instances of this problem: (1) one occurrence per sequence, (2) at most one occurrence per sequence, (3) at least one occurrence per sequence, and (4) any number of occurrences per sequence. The method is implemented in a too] called Nomad (Neighborhood Optimization for Multiple Alignment Discovery) and a web interface is available at www.expasy.org/tools/nomad.html.

• 出版日期2008-3-16