分子进化树算法

计算机研究与发展　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　ＩＳＳＮ　１０００—１２３９／ＣＮ　１１—１７７７／ＴＰ　４５（１１）：１　９６５—１９７３，２００８　

一种基于Ｑｕａｒｔｅｔ　Ｐｕｚｚｌｉｎｇ和邻接法的进化树构建算法　

李建伏　郭茂祖　刘　扬　

（哈尔滨工业大学计算机科学与技术学院　哈尔滨　１５０００１）　（１ｉｊ　ｉａｎｆｕ＠ｈｉｔ．ｅｄｕ．ｃｎ）　

Ａｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｔｒｅｅ　Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ　Ｍｅｔｈｏｄ　Ｃｏｍｂｉｎｉｎｇ　Ｑｕａｒｔｅｔ　Ｐｕｚｚｌｉｎｇ　ａｎｄ　

Ｎｅｉｇｈｂｏｒ　Ｊｏｉｎｉｎｇ　

Ｌｉ　Ｊｉａｎｆｕ，Ｇｕｏ　Ｍａｏｚｕ，ａｎｄ　Ｌｉｕ　Ｙａｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ　１５０００１）　

Ａｂｓｔｒａｃｔ　Ｅｖｏｌｕｔｉｏｎａｒｙ　ｔｒｅｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ　ｉｓ　ａ　ｖｅｒｙ　ｉｍｐｏｒｔａｎｔ　ｔｏｐｉｃ　ｉｎ　ｂｉｏｌｏｇｙ．　Ａ　ｒｅｌｉａｂｌｅ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｔｒｅｅ　ｈａｓ　ｍａｎｙ　ｉｍｐｏｒｔａｎｔ　ａｐｐｌｉｃａｔｉｏｎｓ　ｉｎ　ｍｅｄｉｃａｌ　ａｎｄ　ｂｉｏｌｏｇｉｃａｌ　ｒｅｓｅａｒｃｈ，ｓｕｃｈ　ａｓ　ｄｒｕｇ　

ｄｉｓｃｏｖｅｒｙ　ａｎｄ　ｃｏｎｓｅｒｖａｔｉｏｎ　ｂｉｏｌｏｇｙ．Ａ　ｒｉｃｈ　ｖａｒｉｅｔｙ　ｏｆ　ｔｒｅｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ　ｍｅｔｈｏｄｓ　ｈａｖｅ　ｂｅｅｎ　

ｄｅｖｅｌｏｐｅｄ，ｗｈｉｃｈ　ｆａｌｌ　ｉｎｔｏ　ｔｈｒｅｅ　ｃａｔｅｇｏｒｉｅｓ：１）ｍａｘｉｍｕｍ　ｐａｒｓｉｍｏｎｙ　ｍｅｔｈｏｄｓ，２）ｄｉｓｔａｎｃｅ　ｂａｓｅｄ　ｍｅｔｈｏｄｓ，ａｎｄ　３）ａｐｐｒｏａｃｈｅｓ　ａｐｐｌｙｉｎｇ　ｔｈｅ　ｍａｘｉｍｕｍ　ｌｉｋｅｌｉｈｏｏｄ　ｐｒｉｎｃｉｐｌｅ．Ｍａｘｉｍｕｍ　ｌｉｋｅｌｉｈｏｏｄ　

本 科 毕 业 论 文 第 1 页 共 29 页

1 引言

生物信息学是生物技术的核心，是在分子生物学和信息科学共同发展的基础上产生的一门交叉学科，包含对生物数据的获取、处理、存储、分发、分析、挖掘等方面的研究内容。生物信息学的研究对于最终改善人类自身生活质量，解决健康问题等也有重大的作用。随着分子生物学的不断发展，人们惊奇地发现DNA的双螺旋结构中蕴涵着生命的密码，四种核苷酸的排列、变化包含着许多遗传、进化信息。人类基因组计划以来，有关核酸（或蛋白质）序列和结构的数据成指数增长，而面对如此复杂的数据，计算机在此方面的应用必不可少。因此，生物信息学研究的目的就在于，人们通过数学、计算机科学等各种工具，可以阐明和理解大量数据包含的生物学意义。

由于深度测序和基因芯片技术的不断完善和发展，表达谱、转录组、基因组等数据不断增长。到目前为止，已被测序的昆虫基因至少有10个，被报道的转录组数据也有30多个。生物信息学在昆虫学研究中的应用价值随着昆虫学研究的不断深入和昆虫生物数据的大量积累越来越明显。大量医学昆虫、经济昆虫和农业昆虫的基因组在模式昆虫果蝇的基因组测序成功之后也相继被测序。昆虫种类繁多、进化关系复杂、个体发育系统多样对于生物的多样性组成也占有举足轻重的地位。此外，昆虫与人类的日常生活和生产亦有密切的关系。例如，家蚕、蜜蜂等经济类益虫能够为人类提供日常生产资料和生活资源，害虫能给人类带来巨大的损失。对昆虫基因组进行深入研究不仅能为传统昆虫学科的发展提供崭新的机遇，而且对深入了解昆虫的多样性及其生物学特征与本质具有重大意义。

所有生物都可以追溯到共同的祖先，生物的产生和分化就像树一样的生长，分叉，因此以树的形式来表示生物间的进化关系是非常合理的。根据各类生物间的亲缘关系的远近，把生物安置在树状图表上，简明地表示生物的进化历程和亲缘关系的树状结构就是进化树。在进化树上每个叶子结点代表一个物种，每一条边都被赋予一个适当的权值的话，两个物种之间的差异程度就可以用两个叶子结点间的最短距离来表示。

ＩＳＳＮ　１０００－９８２５，ＣＯＤＥＮ　ＲＵＸＵＥＷ　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，Ｖｏ１．１８，Ｎｏ．３，Ｍａｒｃｈ　２００７，ＰＰ．５０５—５１６　１３ＯＩ：１０．１３６０￣ｏｓ１８０５０５　＠２００７　ｂｙＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ．Ａｌｌ　ｒｉｇｈｔｓ　ｒｅｓｅｒｖｅｄ．　

一种快速的基于占优树的多目标进化算法　

石川。，２＋，李清勇。，　，史忠植。　

‘（中国科学院计算技术研究所智能信息处理重点实验室，北京　１０００８０）　

（中国科学院研究生院，北京１０００４９）　

（北京交通大学计算机与信息技术学院，北京　１０００４４）　

Ａ　Ｑｕｉｃｋ　Ｍｕｌｔｉ－Ｏｂｊｅｃｔｉｖｅ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｄｏｍｉｎａｔｉｎｇ　Ｔｒｅｅ　

ＳＨＩ　Ｃｈｕａｎ　一，ＬＩ　Ｑｉｎｇ．Ｙｏｎｇ　＇　，ＳＨＩ　Ｚｈｏｎｇ—Ｚｈｉ　Ｅ—ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓ．ａｃ．ｃｎ　ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ　Ｔｅｌ，Ｆａｘ：＋８６．１０－６２５６２５６３　

‘（Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｉｎｆｏｒｍａｔｉｏｎ　ｅｒｏＰ￣ｓｓ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，Ｔｈｅ　Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｒｉｎｇ　

１０００８０．Ｃｈｉｎａ）　

（Ｇｒａｄｕａｔｅ　Ｓｃｈｏｏｌ，Ｔｈｅ　Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｄｊｉｎｇ　１０００４９，Ｃｈｉｎａ）　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｒｉｎｇ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００４４，Ｃｈｉｎａ）　

＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ａｕｔｈｏｒ：Ｐｈｎ：＋８６—１０－６２５６５５３３　ｅｘｔ　５６８９，Ｅ－ｍａｉｌ：ｓｈｉｃ＠ｉｃｓ：ｉｃｔ．ａｃ．ｃｎ　

２０１２年第２期　计算机与现代化　ＪＩＳＵＡＮＪＩ　ＹＵ　ＸＩＡＮＤＡＩＨＵＡ　总第１９８期　文章编号：１００６－２４７５（２０１２）０２－００２２－０４　一种改进的进化树构建算法　张立利　，冯萍　，郭宁　（１．西北工业大学计算机学院，陕西西安７１００７２；２．中国人民解放军９１３８８部队，广东湛汪５２４０２２）　摘要：邻接法是最有效的距离建树法的一种，但邻接法的聚类过程总是选择距离最近的进行聚类。容易忽略一些更为合　理的拓扑结构，这是邻接法准确性不够理想的一个重要原因。为了提高邻接法的准确性，本文结合最大似然法提出一种　改进的进化树构建算法。该算法在邻接法基础上，结合最大似然法搜索最优的拓扑结构，通过模拟实验将改进算法与邻　接法等进化树构建算法进行比较，实验结果表明，改进算法的准确性明显优于邻接法。　关键词：进化树；邻接法；最大似然法；ＲＦ距离；启发式搜索　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６－２４７５．２０１２．０２．００７　Ａｎ　Ｉｍｐｒｏｖｅｄ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｃｏｎｓｔｒｕｃｔｉｎｇ　Ｐｈｙｌｏｇｅｎｅｔｉｃ　Ｔｒｅｅ　ＺＨＡＮＧ　Ｌｉ—ｌｉ　，ＦＥＮＧ　Ｐｉｎｇ　，ＧＵＯ　Ｎｉｎｇ　（１．ＣｏＵｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈｗｅｓｔｅｒｎ　Ｐｏｌｙｔｅｃｈｎｉｃａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｌｌ　７１００７２，Ｃｈｉｎａ；　２．９１３８８　ＰＬＡ　Ｔｒｏｏｐｓ，Ｚｈａｎｊｉａｎｇ　５２４０２２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｎｅｉｇｈｂｏｒ－ｊｏｉｎｉｎｇ　ｍｅｔｈｏｄ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｍｏｓｔ　ｅｆｅｃｔｉｖｅ　ｍｅｔｈｏｄｓ　ｂａｓｅｄ　ｏｎ　ｄｉｓｔａｎｃｅ　ｄａｔａ　ｃｏｎｓｔｒｕｃｔｉｎｇ　ｐｈｙｌｏｇｅｎｅｔｉｅ　ｔｒｅｅ．Ｂｕｔ　ｉｔｓ　ｃｌｕｓｔｅｒｉｎｇ　ｐｒｏｃｅｓｓ　ｍａｙ　ｎｅｇｌｅｃｔ　ｓｏｍｅ　ｍｏｒｅ　ｒｅａｓｏｎａｂｌｅ　ｔｏｐｏｌｏｇｉｃａｌ　ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｃａｕｓｅ　ｌｏｗ　ａｃｃｕｒａｃｙ．Ｉｎ　ｏｒｄｅｒ　ｔｏ　ａｄｖａｎｃｅ　ｔｈｅ　ａｃ・　ｃｕｒａｃｙ　ｏｆ　ｎｅｉｇｈｂｏｒ－ｊｏｉｎｉｎｇ　ｍｅｔｈｏｄ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａｎ　ｉｍｐｒｏｖｅｄ　ｍｅｔｈｏｄ．Ｔｈｅ　ｍｅｔｈｏｄ　ｕｓｅｓ　ｎｅｉｇｈｂｏｒ－ｊｏｉｎｉｎｇ　ｍｅｔｈｏｄ　ｔｏ　ｇｅｎｅｒ－　ａｔｅ　ａｌｌ　ｉｎｉｔｉａｌ　ｔｒｅｅ，ａｎｄ　ｔｈｅｎ　ｓｅａｒｃｈｅｓ　ｆｏｒ　ｔｈｅ　ｍａｘｉｍｕｍ—ｌｉｋｅｌｉｈｏｏｄ　ｐｈｙｌｏｇｅｎｅｔｉｃ　ｔｒｅｅ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ＲＦ　ｄｉｓｔａｎｃｅ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｒｅ—　ｓｕｈｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｉｍｐｒｏ￣，ｅｄ　ｍｅｔｈｏｄ　ｉｓ　ｓｕｐｅｒｉｏｒ　ｔｏ　ｎｅｉｇｈｂｏｒ－ｊｏｉｎｉｎｇ　ｍｅｔｈｏｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｐｈｙｌｏｇｅｎｅｔｉｃ　ｔｒｅｅ；ｎｅｉｇｈｂｏｒ－ｊｏｉｎｉｎｇ　ｍｅｔｈｏｄ；ｍａｘｉｍｕｍ　ｌｉｋｅｌｉｈｏｏｄ；ＲＦ　ｄｉｓｔａｎｃｅ；ｈｅｕｒｉｓｔｉｃ　ｓｅａｒｃｈ　０　引　言　系统进化树就是用树状结构来表示物种或者序　列之间的演化关系。高效构建系统进化树对于揭示　物种隐含的种系关系，进行分子进化研究具有重要　意义　¨。　进化树的构建算法根据所利用的数据类型可以　分为两大类：距离法和特征法。距离法　建树利用　的是序列间的距离，将序列信息转化为距离矩阵，在　转化中往往会丢失一些进化信息　Ｊ。基于距离矩阵　的方法有非加权组平均法（即ＵＰＧＭＡ－４　）、邻接法、　Ｆｉｔｃｈ—Ｍａｒｇｏｌｉａｓｈ法　等。邻接法是最常用的一种距　离建树法。特征法则利用基因、个体、群体或物种的　离散特征数据，一般计算量都比较大。基于特征的建　树方法有最大简约法、最大似然法等。最大简约法通　过寻求物种间最小的变更数来完成进化树的构建。　最大似然法则是根据选取的替代模型来分析给定的　一组序列数据，计算每一个可能树的似然值，最后选　取似然值最大的作为最优树。　本文通过分析邻接法建树的优缺点，提出一种基　于邻接法建立初始树，并且结合最大似然法进行启发　式搜索的进化树构建算法。　１邻接法和最大似然法　１．１邻接法　邻接法（Ｎｅｉｇｈｂｏｒ．Ｊｏｉｎｉｎｇ，ＮＪ）是基于最小进化原　理的建树方法，由Ｓａｉｔｏｕ和Ｎｅｉ于１９８７年首次　提出　。　邻接法的建树过程是一个反复进行距离估计和　聚类的过程。距离估计的准确性很大程度上决定了　收稿日期：２０１１．１Ｏ一１７　作者简介：张立利（１９８４．），女，河北行唐人，中国人民解放军９１３８８部队助理工程师，西北工业大学计算机学院硕士婴窭粤，　研究方向：高性能计算；冯萍（１９５５．），女，教授，硕士生导师，博士，研究方向：高性能计算；郭宁（１９８６・），男，河北石家庄人，　硕士研究生，研究方向：嵌入式计算及应用。