SAGA：通过遗传算法进行序列比对。
SAGA: sequence alignment by genetic algorithm.
作者信息
Notredame C, Higgins D G
机构信息
EMBL outstation, The European Bioinformatics Institute, Cambridge, UK.
出版信息
Nucleic Acids Res. 1996 Apr 15;24(8):1515-24. 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.
摘要
我们描述了一种使用遗传算法进行多序列比对的新方法以及一个名为SAGA的相关软件包。该方法涉及以一种准进化方式演化比对群体，并通过一个衡量多序列比对质量的目标函数来逐步提高群体的适应度。SAGA使用一种自动调度方案来控制22种不同操作符的使用，这些操作符用于在各代之间组合比对或使其发生变异。当用于优化著名的双序列和目标函数时，SAGA的表现优于一些广泛使用的其他软件包。这在实现最优解的能力方面以及通过与基于已知三级结构序列的参考比对进行比较的比对准确性方面都有所体现。该方法的普遍吸引力在于能够优化人们可以设想的任何目标函数。
相似文献
1
SAGA: sequence alignment by genetic algorithm.SAGA：通过遗传算法进行序列比对。
Nucleic Acids Res. 1996 Apr 15;24(8):1515-24. doi: 10.1093/nar/24.8.1515.
2
RAGA: RNA sequence alignment by genetic algorithm.RAGA：基于遗传算法的RNA序列比对
Nucleic Acids Res. 1997 Nov 15;25(22):4570-80. doi: 10.1093/nar/25.22.4570.
3
COFFEE: an objective function for multiple sequence alignments.COFFEE：一种用于多序列比对的目标函数。
Bioinformatics. 1998 Jun;14(5):407-22. doi: 10.1093/bioinformatics/14.5.407.
4
Robust sequence alignment using evolutionary rates coupled with an amino acid substitution matrix.使用进化速率结合氨基酸替换矩阵进行稳健的序列比对。
BMC Bioinformatics. 2015 Aug 14;16:255. doi: 10.1186/s12859-015-0688-8.
5
An adaptive and iterative algorithm for refining multiple sequence alignment.一种用于优化多序列比对的自适应迭代算法。
Comput Biol Chem. 2004 Apr;28(2):141-8. doi: 10.1016/j.compbiolchem.2004.02.001.
6
A simple genetic algorithm for multiple sequence alignment.一种用于多序列比对的简单遗传算法。
Genet Mol Res. 2007 Oct 5;6(4):964-82.
7
OXBench: a benchmark for evaluation of protein multiple sequence alignment accuracy.OXBench：一种用于评估蛋白质多序列比对准确性的基准。
BMC Bioinformatics. 2003 Oct 10;4:47. doi: 10.1186/1471-2105-4-47.
8
Multiple sequence alignment with affine gap by using multi-objective genetic algorithm.使用多目标遗传算法进行带仿射间隙的多重序列比对。
Comput Methods Programs Biomed. 2014 Apr;114(1):38-49. doi: 10.1016/j.cmpb.2014.01.013. Epub 2014 Jan 31.
9
Accuracy of structure-based sequence alignment of automatic methods.自动方法的基于结构的序列比对准确性。
BMC Bioinformatics. 2007 Sep 20;8:355. doi: 10.1186/1471-2105-8-355.
10
SeqTools: visual tools for manual analysis of sequence alignments.SeqTools：用于手动分析序列比对的可视化工具。
BMC Res Notes. 2016 Jan 22;9:39. doi: 10.1186/s13104-016-1847-3.
引用本文的文献
1
An nf-core framework for the systematic comparison of alternative modeling tools: the multiple sequence alignment case study.用于替代建模工具系统比较的nf-core框架：多序列比对案例研究
NAR Genom Bioinform. 2025 Jul 31;7(3):lqaf104. doi: 10.1093/nargab/lqaf104. eCollection 2025 Sep.
2
Genetic algorithm for obtaining potential energy curve of diatomic molecules based on dispersed fluorescence spectra.基于色散荧光光谱获取双原子分子势能曲线的遗传算法
Sci Rep. 2023 Oct 13;13(1):17413. doi: 10.1038/s41598-023-44488-7.
3
A Genetic Algorithm for Universal Optimization of Ultrasensitive Surface Plasmon Resonance Sensors with 2D Materials.一种用于二维材料超灵敏表面等离子体共振传感器通用优化的遗传算法。
ACS Omega. 2023 May 26;8(23):20792-20800. doi: 10.1021/acsomega.3c01387. eCollection 2023 Jun 13.
4
Roadmap to the study of gene and protein phylogeny and evolution-A practical guide.基因和蛋白质系统发生与进化研究路线图——实用指南。
PLoS One. 2023 Feb 24;18(2):e0279597. doi: 10.1371/journal.pone.0279597. eCollection 2023.
5
Developments in Algorithms for Sequence Alignment: A Review.序列比对算法的发展：综述。
Biomolecules. 2022 Apr 6;12(4):546. doi: 10.3390/biom12040546.
6
An evolutionary algorithm for designing microbial communities via environmental modification.通过环境改造设计微生物群落的进化算法。
J R Soc Interface. 2021 Jun;18(179):20210348. doi: 10.1098/rsif.2021.0348. Epub 2021 Jun 23.
7
Bacterial Foraging Optimization -Genetic Algorithm for Multiple Sequence Alignment with Multi-Objectives.细菌觅食优化-多目标多序列比对的遗传算法。
Sci Rep. 2017 Aug 18;7(1):8833. doi: 10.1038/s41598-017-09499-1.
8
CamOptimus: a tool for exploiting complex adaptive evolution to optimize experiments and processes in biotechnology.CamOptimus：一种利用复杂适应性进化来优化生物技术实验和流程的工具。
Microbiology (Reading). 2017 Jun;163(6):829-839. doi: 10.1099/mic.0.000477. Epub 2017 Jun 21.
9
IBBOMSA: An Improved Biogeography-based Approach for Multiple Sequence Alignment.IBBOMSA：一种用于多序列比对的改进的基于生物地理学的方法。
Evol Bioinform Online. 2016 Oct 27;12:237-246. doi: 10.4137/EBO.S40457. eCollection 2016.
10
An enhanced algorithm for multiple sequence alignment of protein sequences using genetic algorithm.一种使用遗传算法的蛋白质序列多序列比对增强算法。
EXCLI J. 2015 Dec 15;14:1232-55. doi: 10.17179/excli2015-302. eCollection 2015.
本文引用的文献
1
Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment.提高用于成对总和多序列比对的最短路径方法的实际空间和时间效率。
J Comput Biol. 1995 Fall;2(3):459-72. doi: 10.1089/cmb.1995.2.459.
2
MASCOT: multiple alignment system for protein sequences based on three-way dynamic programming.MASCOT：基于三向动态规划的蛋白质序列多重比对系统。
Comput Appl Biosci. 1993 Apr;9(2):161-7. doi: 10.1093/bioinformatics/9.2.161.
3
Rapid and accurate estimates of statistical significance for sequence data base searches.对序列数据库搜索的统计学显著性进行快速准确的估计。
Proc Natl Acad Sci U S A. 1994 May 24;91(11):4625-8. doi: 10.1073/pnas.91.11.4625.
4
Improved sensitivity of profile searches through the use of sequence weights and gap excision.通过使用序列权重和缺口切除提高轮廓搜索的灵敏度。
Comput Appl Biosci. 1994 Feb;10(1):19-29. doi: 10.1093/bioinformatics/10.1.19.
5
Hidden Markov models in computational biology. Applications to protein modeling.计算生物学中的隐马尔可夫模型。在蛋白质建模中的应用。
J Mol Biol. 1994 Feb 4;235(5):1501-31. doi: 10.1006/jmbi.1994.1104.
6
CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice.CLUSTAL W：通过序列加权、位置特异性空位罚分和权重矩阵选择提高渐进多序列比对的灵敏度。
Nucleic Acids Res. 1994 Nov 11;22(22):4673-80. doi: 10.1093/nar/22.22.4673.
7
Multiple sequence alignment using simulated annealing.使用模拟退火进行多序列比对。
Comput Appl Biosci. 1994 Jul;10(4):419-26. doi: 10.1093/bioinformatics/10.4.419.
8
Optimal sequence alignment using affine gap costs.使用仿射间隙罚分的最优序列比对。
Bull Math Biol. 1986;48(5-6):603-16. doi: 10.1007/BF02462326.
9
Profile analysis: detection of distantly related proteins.轮廓分析：检测远亲相关蛋白。
Proc Natl Acad Sci U S A. 1987 Jul;84(13):4355-8. doi: 10.1073/pnas.84.13.4355.
10
A strategy for the rapid multiple alignment of protein sequences. Confidence levels from tertiary structure comparisons.一种蛋白质序列快速多重比对的策略。来自三级结构比较的置信水平。
J Mol Biol. 1987 Nov 20;198(2):327-37. doi: 10.1016/0022-2836(87)90316-0.
Zotero 插件