SAGA: sequence alignment by genetic algorithm

TitleSAGA: sequence alignment by genetic algorithm
Publication TypeJournal Article
Year of Publication1996
AuthorsNotredame C, Higgins DG
JournalNucleic Acids Res
Volume24
Pagination1515-24
Date PublishedApr 15
Accession Number8628686
KeywordsAlgorithms, Amino Acid Sequence, Molecular Sequence Data, Sequence Alignment, Software
Abstract

We describe a new approach to multiple sequence alignment using genetic algorithms and an associated software package called SAGA. The method involves evolving a population of alignments in a quasi evolutionary manner and gradually improving the fitness of the population as measured by an objective function which measures multiple alignment quality. SAGA uses an automatic scheduling scheme to control the usage of 22 different operators for combining alignments or mutating them between generations. When used to optimise the well known sums of pairs objective function, SAGA performs better than some of the widely used alternative packages. This is seen with respect to the ability to achieve an optimal solution and with regard to the accuracy of alignment by comparison with reference alignments based on sequences of known tertiary structure. The general attraction of the approach is the ability to optimise any objective function that one can invent.