SAGA: sequence alignment by genetic algorithm

Cédric Notredame; Desmond G. Higgins

doi:10.1093/nar/24.8.1515

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.

Keywords

BiologyMultiple sequence alignmentSequence (biology)PopulationSequence alignmentSoftwareAlignment-free sequence analysisFunction (biology)AlgorithmFitness functionGenetic algorithmComputer scienceGeneticsMachine learningPeptide sequence

Affiliated Institutions

European Bioinformatics Institute GB

Related Publications

COFFEE: an objective function for multiple sequence alignments.

Cédric Notredame , Liisa Holm , Desmond G. Higgins

Abstract MOTIVATION: In order to increase the accuracy of multiple sequence alignments, we designed a new strategy for optimizing multiple sequence alignments by genetic algorit...

1998 Bioinformatics 230 citations

RASCAL: rapid scanning and correction of multiple sequence alignments

Julie Thompson , J. C. Thierry , Olivier Poch

Abstract Motivation: Most multiple sequence alignment programs use heuristics that sometimes introduce errors into the alignment. The most commonly used methods to correct these...

2003 Bioinformatics 142 citations

The Jalview Java alignment editor

Michèle Clamp , James Cuff , Stephen M. J. Searle +1 more

Abstract Summary: Multiple sequence alignment remains a crucial method for understanding the function of groups of related nucleic acid and protein sequences. However, it is kno...

2004 Bioinformatics 1538 citations

The CLUSTAL_X windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools

Julie Thompson , Toby J. Gibson , Frédéric Plewniak +2 more

CLUSTAL X is a new windows interface for the widely-used progressive multiple sequence alignment program CLUSTAL W. The new system is easy to use, providing an integrated system...

1997 Nucleic Acids Research 38996 citations

A High-Throughput DNA Sequence Aligner for Microbial Ecology Studies

Patrick D. Schloss

As the scope of microbial surveys expands with the parallel growth in sequencing capacity, a significant bottleneck in data analysis is the ability to generate a biologically me...

2009 PLoS ONE 315 citations

Publication Info

Year: 1996
Type: article
Volume: 24
Issue: 8
Pages: 1515-1524
Citations: 505
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

SAGA: sequence alignment by genetic algorithm

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

505

OpenAlex

Cite This

APA Style

                            
                                    Cédric Notredame, 
                                
                                    Desmond G. Higgins
                                
                            (1996). 
                            SAGA: sequence alignment by genetic algorithm. 
                            Nucleic Acids Research
                            , 24
                            (8)
                            , 1515-1524.
                            https://doi.org/10.1093/nar/24.8.1515

Identifiers

DOI: 10.1093/nar/24.8.1515