【3.1】宏基因组聚类-LCA(Lowest Common Ancestor)

在聚类的过程中,我们常常会使用比对的方法,拿未知的序列跟已知的序列比对,如果这个未知的序列跟谁的相似度最高,我们就认为这个位置的序列属于比对上的那个序列所代表的物种,但是,这里面有一个弊病,很多的未知序列就是属于未知的物种,就不属于任何已知的物种,仅仅是其相似度比跟其他已知序列相似度大就贸然评定它算那个物种,这种想法有待商酌。因此,牛逼哄哄的科学家们引入了一个计算机中的概念LCA(Lowest Common Ancestor,最低共同节点)来让说法更确切一些。

一棵有根樹,樹上兩點的共同祖先當中,離根最遠、深度最深的那一個共同祖先,常簡稱為LCA。

上图是通过best BLAST hit 和LCA算法针对两种不同数据的一个分类。已知的序列(K1),能在相应的数据库中找到。大多数情况下,the best hit指向K1,同时也可能同时跟K2,K3物种相似度很高,使用两种方法best BLAST approach 和 the LCA approach会更准确一些.;来自未知的序列(U1,U2,U3),不在相应的数据库中,如果仅仅根据最好的比对结果,就容易错误的分类,而加入LCA的方法分类就更准确些

因此可以看到,LCA在分类上要比the best hit分类级别上更高一些,但是很好的弥补靠比对带来的误差。

MG-RAST,MEGAN都引入了这方面的算法。MEGAN软件将未知序列和已知序列比对的结果,使用LCA(Least Common Ancestor)算法, 参照NCBI分类学方法将序列进行分类, 分类结果以树状图的方式呈现, 树的节点代表每个分类单元, 匹配到该分类单元的序列数量也会标注出来, 以方便比较这些分类单元在系统发育树上的分布情况。分类结果由序列和分类单元间的匹配特异性程度决定: 特异性程度越低, 分类越偏向于分类树的根部

参考资料

个人公众号,比较懒,很少更新,可以在上面提问题:

更多精彩,请移步公众号阅读:

Sam avatar
About Sam
专注生物信息 专注转化医学