【作者】 刘清雪；

【导师】 马志强；

【作者基本信息】 东北师范大学 ， 计算机软件与理论， 2007， 硕士

【摘要】 系统发生是指生物形成或进化的历史。系统发生学研究物种之间的进化关系,其结果往往是以系统发生树表示。系统发生树是描述物种进化顺序和进化关系的一种拓扑结构。一个可靠的系统发生的推断,将揭示出有关生物进化过程的顺序,有助于我们了解生物进化的历史和进化机制。发生树的构建问题是一个NP完全问题,因此,研究构造发生树的近似最优算法有着重要意义。目前常用的构建发生树的方法有三种,即距离法、最大简约法和最大似然法。本文针对最大简约法,提出了一种新的搜索方法即遗传算法与模拟退火算法相结合的启发示搜索。随机产生初始群体,然后通过遗传退火算子对初始群体进行优化,从中寻找更优树,不断地更新当前最优树,直到无法找到更优树或者达到了搜索次数的上限,算法停止。对改进算法采用了评价建树算法中最常用的计算机模拟法来测试其性能,从实验结果来看,改进算法的准确性都有较大提高。更多还原

【Abstract】 Phylogenetic is history of biology’s evolution.phylogenetic study the relationship of the different species and the result was express by the phylogenetic tree. Phylogenetic tree is a kind of typological structure for describing the sequence and relationship of species revolution. A reliable phylogenetic inference will manifest the sequence of evolution, and facilitate our understanding of the history and mechanism of species evolution.Constructing an evolutionary tree is a typical NP-complete problem,Therefore it is of great significance to construct an algorithm capable of getting optimal approximate solutions. There are three frequently used method: distance method, maximum parsimony method, and maximum likelihood method.A new heuristic search method is devised for maximum parsimony method, which first constructs a group of starting tree by random, and then through Genetic Algorithm and Simulated Annealing Algorithm for trees best resembling the present optimal tree and locates a better tree. Repeat this process, till no more better trees are generated or the upper iteration limit is arrived and the program ends.The adapted algorithms are tested with the most popular method of computer simulation to evaluate tree constructing algorithms. The results show that the accuracy of the improved algorithm is greatly improved.更多还原