层次聚类法(Hierarchical Clustering)构建基于距离的生物进化树

摘 要:

层次聚类法的基本思路是通过迭代分类,把相似的样本放在一层,直到样本都被归到某一层中。层次聚类分为从顶层到底层和从底层到顶层的方法。从顶层到底层是假设有N个待聚类的样本,把每个样本归为一类,计算每两个类之间的距离,寻找最近的两个类归为一类,再计算新生成的类与各个类之间的相似度并归类,整个聚类过程就建立了一棵进化树。

关键词:

层次聚类法的基本思路是通过迭代分类,把相似的样本放在一层,直到样本都被归到某一层中。具体的层次聚类算法分为两种,从顶层到底层的方法和从底层到顶层的方法。

从顶层到底层的算法思想是:假设有N个待聚类的样本,对于层次聚类来说,基本步骤就是:

(1)(初始化)把每个样本归为一类,计算每两个类之间的距离,也就是样本与样本之间的相似度;

(2)寻找各个类之间最近的两个类,把他们归为一类(这样类的总数就少了一个);

(3)重新计算新生成的这个类与各个旧类之间的相似度;

(4)重复2和3直到所有样本点都归为一类,结束。

整个聚类过程其实是建立了一棵树,在建立的过程中,可以通过在第2步上设置一个阈值,当最近的两个类的距离大于这个阈值,则认为迭代可以终止。

从底层到顶层的层次聚类方法与前者描述的由顶层至底层算法相似,只是在进化树形成顺序上是从叶子节点到根节点。

先通过序列比对计算生物之间的进化距离,然后运用层次聚类方法对生物样本进行分类,最终生成层次聚类结果以二叉树形式表现。与基于距离的其他方法如邻接法(Neighbor Joining,NJ)、UPGMA等进化树构建方法以及基于统计特征的最大似然法(Maximum Likelihood,ML),基于生物表现特征的最大简约法(Maximum Parsimony,MP)等生成的进化树进行比较以验证层次聚类方法的可行性,以及如何提高进化树的准确率。

层次聚类法(Hierarchical Clustering)构建基于距离的生物进化树

生物之间进化距离的计算是通过比较DNA序列得到的。序列的比对有两两比对和多重比对之分。比对算法有blast、clustal、fasta等。

    A+

除注明外,本站内容由 细菌之家 原创或整理,转载请注明出处及链接。

本文永久链接: http://www.bacteria.cn/html/2014/968.html

  • 请您留言:专业水平所限,谬误之处在所难免。如您发现不正之处,请在下面留言,谢谢!

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

图片 表情