基于遗传算法的最大似然法构建系统发生树[1]

《基于遗传算法的最大似然法构建系统发生树[1]》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第40卷第1期东北师大学报(自然科学版)Vol.40No.12008年3月JournalofNortheastNormalUniversity(NaturalScienceEdition)March2008[文章编号]100021832(2008)0120036204基于遗传算法的最大似然法构建系统发生树112112李军令,赵宏伟,马志强,魏利,冯嘉,关伟州(1.吉林大学计算机科学与技术学院,吉林长春130012;2.东北师范大学计算机学院,吉林长春130024)[摘要]给出了一种基于遗传算法的最大似然法的建树方法,它是

2、基于遗传算法的搜索最大似然树的启发式方法,将产生最优树和很多准最优树.这种技术在每次循环中只产生一棵树,并且在同代中没有重复的树出现.所以,结果树中含有最优树和很多准最优树,从而大大提高了搜索的效率.[关键词]遗传算法;系统发生;最大似然[中图分类号]TP30116[学科代码]520·10[文献标识码]A1最大似然法1.1理论基础最大似然法(ML)基于两条基本假设:不同的性状进化是独立的;物种发生分歧后进化独立.在ML法中,以一个特定的替代模型分析既定的一组序列数据,使所获得的每一个拓扑结构的似然率均为最大,挑出其最大似

3、然率的最大拓扑结构为最终树.所考虑的参数不是拓扑结构而是每个拓扑结构的枝长,并对似然率求最大值来估计枝长.1.2最大似然法(ML)的计算过程我们首先看一下怎样计算一个给定的DNA树的似然值.考虑一个简单的四类群的树,见图1(A),并假定这个DNA序列为n个核苷酸长,且没有插入或缺失.已知序列1,2,3和4的某个位点(第k个位点)的核苷酸分别位于x1,x2,x3和x4,但并不知道节点0,5和6的核苷酸,而是假设它们分别位于x0,x5和x6.这里xi代表A,T,C,G中的任一种核苷酸.图1含有四个分类群的有根树和无根树[收稿

4、日期]2007210203[基金项目]国家自然科学基金资助重点项目(60433020)[作者简介]李军令(1982—),男,硕士研究生,主要从事生物信息学与智能信息系统研究;赵宏伟(1962—),男,博士后,教授,主要从事智能信息系统及嵌入式技术,智能控制与机器人研究;马志强(1963—),男,博士,教授,主要从事计算机智能和生物信息学研究.第1期李军令,等:基于遗传算法的最大似然法构建系统发生树37第k个核苷酸位点的似然函数为lk=gx0Pxx(v5)Pxx(v1)Pxx(v2)Pxx(v6)Pxx(v3)Pxx(v4

5、),(1)055152066364这里,Pij(t)表示给定位点在时间0时的核苷酸i到时间t变位核苷酸j的概率,gx是接点0为核苷酸0x0时的先验概率.gx常常等于核苷酸x0在整个序列中的相对频率.0为了计算,Pij(v)必须使用一个特定的替代模型.目前使用较多的是一些相对简单的模型,如Jukes2Cantor模型,Kimura二参数模型及一般二参数模型.其中Felsentein使用了等输入模型,在这个模[1]型中:-y1/4+(1-gi)em,j=i;Pij(y)=(2)-y)1/4(1-em,j≠i.这里,vm表示分

6、枝m上的核苷酸替代数目,gi表示核苷酸i在整个序列中的相对频率.在以上公式中,我们考虑了有根树.然而,如果我们用一个可逆的核苷酸替代模型来定义Pij(v),就没有必要考虑树根,见图1(B).可逆模型意味着时间0到t之间,核苷酸替代的过程不变,不管我们是考虑向前还是向后的进化过程.数学上,这个可逆条件为giPij(v)=gjPji(v).(3)对任意的i和j,公式(2)满足这个条件.只要使用可逆模型,树A的节点5和6之间的核苷酸替代数(v5+v6)就可保持恒定而与根0的位置无关.因此,计算lk时,我们指定树A的v5+v6位

7、树B的v5,并假设进化改变开始于该树的某一点.为方便起见,假定从节点5开始,从而大大地简化了计算.我们可以将公式(1)改写为:lk=gxPxx(v1)Pxx(v2)Pxx(v6)Pxx(v3)Pxx(v4).(4)55152566364当然,实际上我们并不知道x5和x6,因而这个似然率为节点5和6的所有可能的核苷酸之总和.即lk=∑∑gxPxx(v1)Pxx(v2)Pxx(v6)Pxx(v3)Pxx(v4).(5)xx5515256636456到目前为止,我们仅仅考虑了一个核苷酸位点.实际上,我们必须考虑包括不变位点在内

8、的所有核苷酸位点.整个序列的似然率(L)是对所有位点的LK求积,则整个树的似然率对数为:nlnL=∑lnLk.(6)k=1我们可以通过改变参数vt使lnL最大化,最大化能对这个拓扑结构的分枝长度给出ML估计.要找出最大似然树,必须考虑所有可能的拓扑结构,并对每棵树都求出其最大似然值,然后选出最大的那棵即为所求.2基于