网易 
新闻 LOFTER 邮箱 相册 阅读 图书 有道 摄影 企业邮箱 优惠券 云笔记 闪电邮 邮箱大师 印像派 考拉海购
 
更多
博客 
手机博客 博客搬家 博客VIP服务 发现 小组 风格
 
群博客 博客油菜地 博客话题 博客热点 博客圈子 找朋友
 
登录  
 加关注
   显示下一条  |  关闭
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！立即重新绑定新浪微博》  |  关闭

云之南

风声，雨声，读书声，声声入耳；家事，国事，天下事，事事关心

导航

 
 
 
 
 

日志

 
 
关于我
云之南

专业背景：计算机科学 研究方向与兴趣: JavaEE-Web软件开发, 生物信息学, 数据挖掘与机器学习, 智能信息系统 目前工作: 基因组, 转录组, NGS高通量数据分析, 生物数据挖掘, 植物系统发育和比较进化基因组学

文章分类

生物信息学精讲——进化树  

2010-01-05 19:39:06|  分类： 进化与系统学 |  标签： |举报 |字号大中小 订阅

  下载LOFTER 我的照片书  |

分子钟的发现对于进化研究具有十分重要的意义。它不仅能用于粗略估计不同类群生物间的进化时间，亦可用于构建进化树。实际上，分子钟发现不久，蛋白质序列分析即被广泛用于生物的长时进化研究。

根据蛋白质的序列或结构差异关系可构建分子进化树(evolutionary tree)或种系发生树(phylogenetic tree)。进化树给出分支层次或拓扑图形，它是产生新的基因复制或享有共同祖先的生物体的歧异点的一种反映，树枝的长度反映当这些事件发生时就存在的蛋白质与现在的蛋白质之间的进化距离。根据进化树不仅可以研究从单细胞有机体到多细胞有机体的生物进化过程，而且可以粗略估计现存的各类种属生物的分歧时间。通过蛋白质的分子进化树分析，为从分子水平研究物种进化提供了新的手段，可以比较精确的确定某物种的进化地位。对于物种分类问题，蛋白质的分子进化树亦可作为一个重要的依据。

构建进化树的方法包括两种：一类是序列类似性比较，主要是基于氨基酸相对突变率矩阵（常用PAM250）计算不同序列差异性积分作为它们的差异性量度（序列进化树）；另一类在难以通过序列比较构建序列进化树的情况下，通过蛋白质结构比较包括刚体结构叠合和多结构特征比较等方法建立结构进化树。

序列进化树

构建序列进化树的主要步骤是比对，建立取代模型，建立进化树以及进化树评估。 1．建立数据模型（比对）

建立一个比对模型的基本步骤包括：选择合适的比对程序；然后从比对结果中提取系统发育的数据集，至于如何提取有效数据，取决于所选择的建树程序如何处理容易引起歧义的比对区域和插入/删除序列（即所谓的indel状态或者空位状态）。一个典型的比对过程包括：首先应用CLUSTALW程序，然后进行手工比对，最后提交给一个建树程序。这个过程有如下特征选项：（1）部分依赖于计算机（也就是说，需要手工调整）；（2）需要一个先验的系统发育标准（即需要一个前导树）；（3）使用先验评估方法和动态评估方法（推荐）对比对参数进行评估；（4）对基本结构（序列）进行比对（对于亲水氨基酸，推荐引入部分二级结构特征）；（5）应用非统计数学优化。这些特征选项的取舍依赖于系统发育分析方法。 2．决定取代模型

取代模型既影响比对，也影响建树；因此需要采用递归方法。对于核酸数据而言，可以通过取代模型中的两个要素进行计算机评估，但是对于氨基酸和密码子数据而言，没有什么评估方案。其中一个要素是碱基之间相互取代的模型；另外一个要素是序列中不同位点的所有取代的相对速率。还没有一种简单的计算机程序可以对较复杂的变量（比如，位点特异性或者系统特异性取代模型）进行评估，同样，现有的建树软件也不可能理解这些复杂变量。 3．建树方法

三种主要的建树方法分别是距离、最大节约（maximum parsimony, MP）和最大似然（maximum likelihood，ML）。最大似然方法考察数据组中序列的多重比对结果，优化出拥有一定拓扑结构和树枝长度的进化树，这个进化树能够以最大的概率导致考察的多重比对结果。距离树考察数据组中所有序列的两两比对结果，通过序列两两之间的差异决定进化树的拓扑结构和树枝长度。最大节约方法考察数据组中序列的多重比对结果，优化出的进化树能够利用最少的离散步骤去解释多重比对中的碱基差异。

距离方阵方法简单的计算两个序列的差异数量。这个数量被看作进化距离，而其准确大小依赖于进化模型的选择。然后运行一个聚类算法，从最相似（也就是说，两者之间的距离最短）的序列开始，通过距离值方阵计算出实际的进化树，或者通过将总的树枝长度最小化而优化出进化树。用最大节约方法搜索进化树的原理是要求用最小的改变来解释所要研究的分类群之间的观察到的差异。最大似然方法评估所选定的进化模型能够产生实际观察到的数据的可能性。进化模型可能只是简单地假定所有核苷酸（或者氨基酸）之间相互转变的概率一样。程序会把所有可能的核苷酸轮流置于进化树的内部节点上，并且计算每一个这样的序列产生实际数据的可能性（如果两个姐妹分类群都有核苷酸“A”，那么，如果假定原先的核苷酸是“C”，得到现在的“A”的可能性比起假定原先就是“A”的可能性要小得多）。所有可能的再现（不仅仅是比较可能的再现）的几率被加总，产生一个特定位点的似然值，然后这个数据集的所有比对位点的似然值的加和就是整个进化树的似然值。 4．进化树搜索

单一的进化树的数量会随着分类群数量的增长而呈指数增长，从而变为一个天文数字。由于计算能力的限制，现在一般只允许对很小一部分的可能的进化树进行搜索。具体的数目主要依赖于分类群的数量、优化标准、参数设定、数据结构、计算机硬件以及计算机软件。有两种搜索方法保证可以找到最优化的进化树：穷举法和树枝跳跃法（BB）。对于一个很大的数据集，这两种方法都很不实用。对分类群数量的限制主要取决于数据结构和计算机速度，但是对于超过20个分类群的数据集，BB方法很少会得到应用。穷举法要根据优化标准，对每一个可能的进化树进行评估。BB方法提供一个逻辑方法，以确定那些进化树值得评估，而另一些进化树可被简单屏蔽。因此BB方法通常要比穷举法快得多。

绝大多数分析方法都使用“启发式”的搜索。启发式现搜索出相近的次优化的进化树家族（“岛屿”），然后从中得到优化解（“山顶”）。不同的算法用不同程度的精确性搜索这些岛屿和山顶。最彻底也是最慢的程序（TBR，tree bisection-reconnection，进化树对分重接）先把进化树在每一个内部树枝处劈开，然后以任意方式将劈开的碎片重新组合起来。最快的算法只是检查一下相邻终端的不太重要的重新组合，因此倾向于找到最近的岛屿的山顶。降低搜索代价的最好方法是对数据集进行剪除。影响优化搜索策略选择的因素（数据量，数据结构，时间量，硬件，分析目的）太复杂，无法推荐一个简单可行的处方。因此进行搜索的用户必须对数据非常熟悉且有明确的目标，了解各种各样的搜索程序及自己硬件设备和软件的能力。

除上述当前应用最广的方法外，还有大量的建立和搜索进化树的其它方法。这些方法包括Wagner距离方法和亲近方法（距离转化方法）；Lake的不变式方法（一个基于特征符的方法，它选择的拓扑结构包含一个意义重大的正数以支持颠换）；Hadamard结合方法（一个精细的代数方阵方法，对距离数据或者观察到的特征符进行修正）；裂解方法（这个方法决定在数据中应该支持哪一个基于距离的可选的拓扑结构）；四重奏迷惑（Quartet puzzling）方法可以为ML建树方法所应用，这个算法相对而言是个较快的进化树搜索算法。 5．确定树根

上述的建树方法所产生的都是无根树（进化树没有进化的极性）。为了评估进化假说，通常必须要确定进化树的树根。确定系统发育进化树的树根并不简单问题。一种确定树根的好方法就是分析时加入一个复制的基因。如果来自绝大多数物种或者所有物种的所有的平行基因在分析时都被包含进去，那么从逻辑上我们就可以把进化树的树根定位于平行基因进化树的交汇处，当然要假定在所有进化树中都没有长树枝问题。 6．评估进化树和数据

现在已经有一些程序可以用来评估数据中的系统发育信号和进化树的健壮性。对于前者，最流行的方法是用数据信号和随机数据作对比实验（偏斜和排列实验）；对于后者，可以对观察到的数据重新取样，进行进化树的支持实验（非参数自引导和对折方法）。似然比例实验可以对取代模型和进化树都进行评估。

结构进化树

随着X－ray、NMR等实验技术的的进步，蛋白质结构数据的数量日益增多，结构精度也越来越高，使得结构比较更为可行。目前已经发现许多蛋白的一级序列差异很大，难以通过序列比对进行分子进化的研究，但它们的空间拓扑结构仍然很相似，可以进行结构叠合比较、分析它们之间的进化关系，这表明结构比较可以比序列比较获得更多更精确的结构信息。研究发现蛋白质结构比序列的保守性更强，进化过程中蛋白质序列可能发生变化，但它的折叠模式更为保守，即使是70％的序列发生变化，它的折叠模式也不会有很大的改变。蛋白质分子的结构比较与蛋白质一级序列比较法相比，具有更高的优越性。

目前有关蛋白质结构比较的研究方法很多，主要有刚体结构叠合比较、多特征的结构比较等方法。前者用比较后确定的拓扑等价位点的个数或等价位点Cα原子距离的均方根值作为不同结构间差异性的量度（结构进化树）；后者用蛋白质结构的多项特征如残基的物理特性、残基的空间倾向性、主侧链的方向、主链的二面角、二级结构类型和主侧链的可接近性等综合指标作为结构的差异性量度，有时称此类方法构建的结构进化树为“类结构”进化树。

刚体叠合所构建的进化树适用于同源蛋白质结构预测的骨架结构的选择，基于序列的进化树便于描述类似性较大的蛋白质的进化关系，而结构的多特征比较则适用于分析分歧较大的蛋白质结构。 1．刚体结构叠合比较

当已知2个以上同源蛋白质的晶体结构时，可将每两套结构的原子坐标进行最佳叠合，确定类似结构中完整的一套残基等价位点，并使等价位点间的距离平方和最小，这样便得到各结构的拓扑等价区。通常将结构简化为一系列Cα位置，等价位点被定义为在重叠结构中位于某个特定距离范围（不大于3埃）之内的Cα原子。通过计算不同结构等价位点的个数或计算多个结构的等价位点Cα距离的均方根值作为不同结构间差异性的度量。再根据一般的建树方法，给出几个结构的进化关系。

刚体结构叠合方法需要蛋白质的晶体结构数据的质量要高。事实上，相对于序列而言，已测定的蛋白质晶体结构很少，许多同源蛋白质的结构并不知道。其次，尽管同源蛋白质具有相同的折叠结构，它们的二级结构成分则经历形变、相对平移和旋转使侧链达到优化的包装以适应进化的压力。对于序列相同率为30%的两个蛋白质，由刚体叠合所确定的拓扑等残基的均方根差大约为1.5埃，而且残基数可能只占全部残基数的1/3。它可能不足以进行结构比较。因此需要发展一种更灵活的确定拓扑等价位点的方法，并且要把二级结构成分的相对运动和变形也考虑进去。 2．多特征结构比较

多特征结构比较以及构建“类结构”进化树的原理与基于残基匹配记分方法（常用PAM250矩阵）进行多序列比较和构建序列进化树的原理相同。包括以下步骤：（1）动态规划配准和结构匹配；（2）多个结构的多特征比较；（3）多特征结构比较的距离量度；（4）绘制进化树图。

相关软件 Phylip

PHYLIP是一个包含了大约30个程序的软件包，这些程序基本上囊括了系统发育的所有方面。PHYLIP是免费软件，并且可以在很多平台上运行（Mac, DOS, Unix, VAX/VMS, 及其它）。PHYLIP目前已经是最广泛使用的系统发育程序。 PAUP

开发PAUP的目的是为系统发育分析提供一个简单的，带有菜单界面的，与平台无关的，拥有多种功能（包括进化树图）的程序。PAUP 3.0只建立于MP相关的进化树及其分析功能；而PAUP 4.0已经可以针对核苷酸数据进行与距离方法和ML方法相关的分析功能，以及其它一些特色。

除了PAUP和PHYLIP以外，还有其它一些系统发育程序，这些程序包括：FastDNAml, MACCLADE, MEGA plus METREE, MOLPHY和PAML PHYLOGENETIC RESOURCES

http://www.ucmp.berkeley.edu/subway/phylogen.html

PHYLOGENY PROGRAMS

http://evolution.genetics.washington.edu/phylip/software.html

PHYLOGENETIC ANALYSIS COMPUTER PROGRAMS

http://phylogeny.arizona.edu/tree/programs/programs.html

BIOCATALOG MOLECULAR EVOLUTION

http://www.ebi.ac.uk:/biocat/phylogeny.html

PHYLIPhttp://evolution.genetics.washington.edu/phylip.html

想学建树的都要看看Nei那本绿皮书的相关章节。结合我个人的经验，补充几句。

先说方法的选择。有三种nj（距离法的代表）, parsimony（最大简约）, ml（极大似然）。一般来讲，如果模型合适，ml的效果最好。对近缘序列，有人喜欢parsimony，因为用的假设最少(的确很诱人)。其实其它方法都会很好，模型间的差别也不大。parsimony一般不用在远缘序列上，这时一般用nj或ml。对相似度很低的序列，nj往往出现long-branch attraction，有时严重干扰构树。ml据说影响最小(某篇review说的)。

nj和ml是需要选择模型的。先说nj。nj的模型是用来算距离矩阵的，主要分极大似然模型，和mismatch模型(或p-distance)。一般人们喜欢复杂的模型（HKY84 for nucleotide, and JTT, WAG, ... for amino acids），但p-distance对远缘序列往往有更好的效果。nei的书中有很好的评述，我的经验也是如此。还有一种叫kimura校正的，其实是p-distance在蛋白的推广。clustalw有这个选项，实际效果我认为反而不好。

ml用的都是极大似然模型。tree-puzzle的文档对各种模型的选择做了很好的评述。其实实用中差别可能并不大。没经验。

至于软件，ml树推荐用phyml，速度最快，或用paml，名气最大；parsimony推荐用老牌paup，但mega或phylip也能做，我不常做parsimony；nj的选择就太多了，出于名气考虑，可以用phylip(但写得有点问题，过慢，bootstrap不方便)，clustalw(只有p-distance，模型太少，但用着很舒服)，mega(没用过)。

tree-puzzle是个好软件，用的是所谓的四级ml近似，效果不如ml，但一般比nj好一点。建议用tree-puzzle代替phylip算距离矩阵，快的多。tree-puzzle还有许多实用功能。mega应该是个好软件，功能很多，很强。但只有windows版。我不用。这些都是有名气的，其实有许多更优秀的软件仅仅由于名气原因不为人所知。闲人们可以去phylip的网站看看。我不在这里瞎介绍了。

另外，很近缘序列一般用nucleotide，有时蛋白根本没区别；远的一定要用amino acids。画nucleotide树，如果在cds上，一般先做amino acids alignment，再反过来对应到nucleotide，可以用Emboss的tranalign程序，不过还是很麻烦。由于进化压力问题，对近缘序列，dS树有时效果最好，但现在画这种树很麻烦，不知mega是否有这个功能。

PS:实用中，只要方法、模型合理，建出的树都有意义，可以随便选择自己认为好一个，或用tree fusion合并，不过这么做的人不多。如果写进化树的paper，各种方法和模型都要试试。

高手们可以来补充，我也学习一下。先谢谢了。

mediocrebeing 于dxy 2005-09-08 16:25

有关进化树分析的一些方法学问题

http://www.dxy.cn/bbs/actions/archive/post/150322_1.html

进化树也称种系树，英文名叫“Phyligenetic tree”。对于一个完整的进化树分析需要以下几个步骤：

⑴ 要对所分析的多序列目标进行排列（To align sequences）。做ALIGNMENT的软件很多，最经常使用的有CLUSTALX和CLUSTALW，前者是在WINDOW下的而后者是在DOS下的。

⑵ 要构建一个进化树（To reconstrut phyligenetic tree）。构建进化树的算法主要分为两类：独立元素法（discrete character methods）和距离依靠法（distance methods）。所谓独立元素法是指进化树的拓扑形状是由序列上的每个碱基/氨基酸的状态决定的（例如：一个序列上可能包含很多的酶切位点，而每个酶切位点的存在与否是由几个碱基的状态决定的，也就是说一个序列碱基的状态决定着它的酶切位点状态，当多个序列进行进化树分析时，进化树的拓扑形状也就由这些碱基的状态决定了）。而距离依靠法是指进化树的拓扑形状由两两序列的进化距离决定的。进化树枝条的长度代表着进化距离。独立元素法包括最大简约性法（Maximum Parsimony methods）和最大可能性法（Maximum Likelihood methods）；距离依靠法包括除权配对法（UPGMAM）和邻位相连法（Neighbor-joining）。

⑶ 对进化树进行评估。主要采用Bootstraping法。进化树的构建是一个统计学问题。我们所构建出来的进化树只是对真实的进化关系的评估或者模拟。如果我们采用了一个适当的方法，那么所构建的进化树就会接近真实的“进化树”。模拟的进化树需要一种数学方法来对其进行评估。不同的算法有不同的适用目标。

一般来说，最大简约性法适用于符合以下条件的多序列：i 所要比较的序列的碱基差别小，ii 对于序列上的每一个碱基有近似相等的变异率，iii 没有过多的颠换/转换的倾向，iv 所检验的序列的碱基数目较多（大于几千个碱基）；用最大可能性法分析序列则不需以上的诸多条件，但是此种方法计算极其耗时。如果分析的序列较多，有可能要花上几天的时间才能计算完毕。UPGMAM（Unweighted pair group method with arithmetic mean）假设在进化过程中所有核苷酸/氨基酸都有相同的变异率，也就是存在着一个分子钟。这种算法得到的进化树相对来说不是很准确，现在已经很少使用。邻位相连法是一个经常被使用的算法，它构建的进化树相对准确，而且计算快捷。其缺点是序列上的所有位点都被同等对待，而且，所分析的序列的进化距离不能太大。

另外，需要特别指出的是对于一些特定多序列对象来说可能没有任何一个现存算法非常适合它。最好是我们来发展一个更好的算法来解决它。但无疑这是非常难的。（转贴自tanjie的网站）

标 题: [范文]进化树构建中常用的MP与ML，及相关的软件介绍

标  题: [范文]进化树构建中常用的MP与ML，及相关的软件介绍

发信站: 水木社区 (Thu Sep  8 12:47:01 2005), 站内

        Phylogenetic trees reconstruct relationships between species or individu

als using molecular data.   Two commonly used methods for reconstructing relatio

nships are maximum likelihood (ML) and maximum parsimony (MP).   Maximum likelih

ood evaluates a hypothesis about evolutionary history in terms of the probabilit

y that the proposed model and the hypothesized history would give rise to the ob

served data set.   The topology with the highest maximum probability (likelihood

) is chosen.   Maximum parsimony infers a phylogenetic tree by minimizing the to

tal number of evolutionary steps required to explain a given set of data.

Maximum Likelihood

        Advantages of maximum likelihood methods over other methods are: may hav

e lower variance than other methods (least affected by sampling error), tend to

be robust to violations of the assumptions in the evolutionary model, are statis

tically well founded, can statistically evaluate different tree topologies and u

se all of the sequence information.   There are also some disadvantages: very co

mputationally intensive (slow) and the result depends on the model of evolution

(Opperdoes, 1997a).

         There are four maximum likelihood programs available on iNquiry.

Program Data

Tree-Puzzle DNA or Protein sequence

PAML (CODEML) DNA or Protein sequence

DNAML (PHYLIP) DNA sequence

fastDNAml DNA sequence

Tree-Puzzle

Tree-Puzzle is a program for maximum likelihood analysis of DNA or protein seque

nce data.   This program implements a fast tree search algorithm, quartet puzzli

ng, that allows analysis of large data sets and automatically assigns estimation

s of branch support to each internal branch.   It also computes pairwise maximum

likelihood distances as well as branch lengths for user specified trees.

Input: Sequence input is requested as an alignment file in PHYLIP interleaved fo

rmat.   The user must choose the type of sequence, DNA or protein.

Options: The user may choose the model of substitution to be applied, HKY (Haseg

awa et al 1985) is the default for DNA and Dayhoff (Dayhoff et al. 1978) is the

default for protein sequence.   The user may input the transition/transversion r

atio and nucleotide frequencies, however if these are left blank the program wil

l estimate them from the data set.   There are options for the model of rate het

erogeneity, the default is uniform rate.   The last two options are for a user-s

pecified tree and the output options.   In the output the user may specify a seq

uence to be designated as the outgroup, this should be the number of the individ

ual in the alignment file (for example, the first sequence would be 1, the fourt

h sequence would be 4).

Output: Tree-Puzzle, when used with the default options, gives a summary of the

sequence data input, maximum likelihood distances, an quartet puzzling tree and

any other trees that occurred more than 5% of the time in the 1000 (default) puz

zling steps.

MAXIMUM LIKELIHOOD BRANCH LENGTHS ON QUARTET PUZZLING TREE (NO CLOCK)

Branch lengths are computed using the selected model of

substitution and rate heterogeneity.

            :----3 AF157877

       :----6

       :    :----------4 AF157953

:-----7

:     :----------------------5 GVO389531

:

:---2 AF157941

:

:--1 AF157928

         branch  length     S.E.   branch  length     S.E.

AF157928      1  0.01919  0.00460     6  0.02588  0.00694

AF157941      2  0.02246  0.00491     7  0.03991  0.00797

AF157877      3  0.03741  0.00725

AF157953      4  0.10455  0.01119     8 iterations until

                                        convergence

GVO389531     5  0.23022  0.01835     log L: -3347.60

Quartet puzzling tree with maximum likelihood branch lengths

(in CLUSTAL W notation):

(AF157928:0.01919,((AF157877:0.03741,AF157953:0.10455)51:0.02588,

GVO389531:0.23022)100:0.03991,AF157941:0.02246);

PAML

In the PAML package on iNquiry is the program codeml, which does maximum likelih

ood for DNA or protein sequence.   Two old PAML programs, baseml and codonml, we

re combined to create codeml.

Input: DNA or protein sequence may be directly pasted in or a file may be specif

ied.   The sequence data must have the number of sequences and the number of cha

racters, followed by the sequence name, then the sequence (see example input for

ProtPars).   The user may also input a tree structure file.

Options: There are options for the general run of the program and ones specific

for DNA and protein.   The common options are for the output file names, the typ

e of sequence, the tree, and other parameters for estimating trees.   It is very

important to specify the tree to be used (the user must choose an option from t

he pull-down list, the default is 0, or user-specified tree, if not supplying a

tree).   Codon sequence options are for DNA sequence data and include model, cod

on frequency, genetic code, kappa and omega values.   It is very important to sp

ecify the genetic code to be used (the default of 0, universal code does not wor

k for mammalian mitochondrial DNA sequence).   Amino acid sequence options are t

he model, alpha and the matrix.   If the empirical models are chosen from the pu

lldown menu the user must specify a matrix file.

Output: There are three output files from paml: rst gives codon sites with posit

ion differences and star trees, mlc gives site patterns, sequence differences, c

odon usage in sequences, a distance matrix and the best tree.

best tree: (((1, 2), 4), 3, 5); lnL: -2853.476553

DNAml

DNAml is part of the PHYLIP package, fastDNAml performs the same functions using

less memory.

fastDNAml

FastDNAml performs unrooted maximum likelihood on aligned DNA sequence.   It is

faster than DNAml and has the ability to save progress toward finding a tree (ca

n be restarted from a checkpoint).

Input: Aligned DNA sequence.

Options: The user may specify the base frequencies or check the box for the prog

ram to derive them from the sequence data.   The user may specify an outgroup (b

y the order of the sequences as in Tree-Puzzle) and the transition/transversion

ratio.   If the interleaved box is left checked the program will convert the seq

uence from FASTA format to PHYLIP interleaved format.   There are options for bo

otstrapping the tree(s) found by the program.   There are also options for the d

isplay of the output and the rearrangements of trees.   The last two options are

for user-specified weights and trees.

Output: The first output file is a tree and the second is a summary of the resul

ts.   It gives the aligned sequences with any variable positions, which are call

ed distinct data patterns.   The program finds an unrooted tree and gives branch

length values and approximate confidence limits.

Maximum Parsimony

        Maximum parsimony methods search all possible tree topologies for the op

timal (or minimal) tree.   Advantages of maximum parsimony are: it is based on s

hared and derived characters, therefore a cladistic method, it tries to provide

information on the ancestral sequences and evaluates different trees.   Disadvan

tages are:   does not use all the sequence information (only informative sites),

does not correct for multiple mutations (no model of evolution), does not provi

de information on branch lengths and it is sensitive to codon bias (Opperdoes, 1

997b).   For more information on parsimony see Felsenstien (2004).   There are t

wo maximum parsimony programs for sequence data available on iNquiry, both are f

rom the PHYLIP package.

Program Data

PROTPARS Protein sequence

DNAPARS DNA sequence

PROTPARS

This program applies a novel method for inferring unrooted phylogeny from protei

n sequences.   The user should consult the fine manual for the program for the a

ssumptions of the method.

Input: Aligned protein sequence, where the first line contains the number of spe

cies and the number of amino acid positions, then the species data.   Each seque

nce starts on a new line, has a ten-character species name, immediately followed

by the species data in one-letter code.

Options: There is an option for using threshold parsimony and specifying the thr

eshold value as well as specifying the genetic code to be used.   There are also

options for randomizing and bootstrapping as well as input for a user-specified

tree.   The user may choose the output options and specify an outgroup, by desi

gnating the sequence by the order (the first sequence is 1, etc.).

Output: The program gives the most parsimonious tree (or trees).

One most parsimonious tree found:

  +-----------05CYB_GLV

  4

  !  +--------04CYB_MAM

  +--3

     !  +-----03CYB_SPT

     +--2

        !  +--02CYB_SPT

        +--1

           +--01CYB_SPM

remember: (although rooted by outgroup) this is an unrooted tree!

requires a total of     64.000

DNAPARS

This program searches bifurcating and multifurcating trees for the most parsimon

ious trees and saves a number of trees tied for best and rearranges all of the s

aved trees.

Input: Aligned protein sequence, where the first line contains the number of spe

cies and the number of amino acid positions, then the species data.   Each seque

nce starts on a new line, has a ten-character species name, immediately followed

by the species data in one-letter code.

Options: There is an option for using threshold parsimony and specifying the thr

eshold value.   There are also options for randomizing and bootstrapping as well

as input for a user-specified tree.   The user may choose the weight and output

options and specify an outgroup, by designating the sequence by the order (the

first sequence is 1, etc.).

Output: The program gives the most parsimonious tree (or trees) and distances.

References

All information contained in this document was obtained from the respective fine

manual of the program or Nei, M. and Kumar, S. 2000. Molecular Evolution and Ph

ylogenetics. Oxford University Press, Inc., New York, unless cited otherwise.

Felsenstein, J. 2004. Statistical properties of parsimony, pp. 97-122 and A digr

ession on history and philosophy, pp. 123-146, in Inferring Phylogenies. Sinaur

Associates, Inc., Sunderland, Massachusetts.

Opperdoes, F. 1997. Maximum Likelihood. Retreived 20 April 2004.http://www.icp.

ucl.ac.be/~opperd/private/max_likeli.html .

Opperdoes, F. 1997. Maximum Parsimony Analysis. Retreived 20 April 2004. http://

www.icp.ucl.ac.be/~opperd/private/parsimony.html .

多序列比对与进化树间的关系(zz)

发信人: chevalier (burn myself to warm her), 信区: Board_Apply

标  题: [范文]多序列比对与进化树间的关系

发信站: 水木社区 (Thu Sep  8 12:45:57 2005), 站内

简单回答一下polyhedron的疑问 ：）

首先，多序列比对的结果是不确定的，没有一个最终正确的解，而是根据不同的算法和条件，会有不同的最优解(optimal)；

Clustal的算法，简单来说，是这样子的把所有n个sequences两两比对；

2. 根据Neighbor-Joining的原则以及上述计算结果，生成一个NJ Tree

接下来的步骤是源于一个技巧，就是：

每个对比后的sequence pair (alignment)都可以跟第三条序列或者另一个新的alignment

比对，这是算法上可以实现的。

所以，第三步是这样的：假定NJ Tree 是这样的： (A,B),(C,D)

3. 首先，比对closest pair: AB；然后，比对second closest pair: CD

最后，比对AB 和 CD， 这样得出最终的alignment结果

如果 NJ Tree 是这样的： ((A,B),C),D

那么，首先比对A,B, 然后比对 AB,C； 最后，比对ABC,D

显然，第二步得到的NJ Tree起到指导的作用，按照距离远近，用来决定下一个参与比对的sequence 或者 alignment

4. 根据最终的alignment结果，便可以做ML(Maximum Likelihood) or MP (MaximumPasimony) 进化树了。它们又有不同的算法，具体来讲，MP的原则是亲缘关系近的序列具有较小的序列变化；而ML，顾名思义，便是具有较大的likelihood.

  评论这张
 
阅读(5342)| 评论(0)

历史上的今天

评论

<#--最新日志，群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇，下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

我的照片书 - 手机博客 - 下载LOFTER APP - 订阅此博客

网易公司版权所有 ©1997-2018