 |
    |
Evolving Consensus Sequence for Multiple Sequence Alignment with a Genetic Algorithm
Conrad Shyu and James A. Foster
Initiatives for Bioinformatics and Evolutionary Studies (IBEST)
Department of Computer Science
University of Idaho
Moscow, Idaho 83843, USA
{tsemings,foster}@cs.uidaho.edu
Abstract. In this paper we present an approach that evolves the consensus sequence [25] for multiple sequence alignment (MSA) with genetic algorithm (GA). We have developed an encoding scheme such that the number of gene-rations needed to find the optimal solution is approximately the same regardless the number of sequences. Instead it only depends on the length of the template and similarity between sequences. The objective function gives a sum-of-pairs (SP) score as the fitness values. We conducted some preliminary studies and compared our approach with the commonly used heuristic alignment program Clustal W. Results have shown that the GA can indeed scale and perform well.
LNCS 2724, p. 2313 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003