近邻结合法
生物学术语
近邻结合法,neighbor-joining method,应用领域演化生物学
简介
近邻相接法(neighbor-joining method)是一种研究DNA而建立亲缘关系的方法,在计算生物学生物信息学系统生物学演化生物学系统发生学中时常使用。该方法,后来也应用在电脑算法之中。
该法依赖距离矩阵资料,由序列建立支序图或亲缘关系图的方法。先由序列算出每一对细菌间的演化距离,将所有的演化距离资料整理成一个距离矩阵,再利用距离矩阵的资料画出树型
距离矩阵
数学中, 一个距离矩阵是一个包含一组两两之间距离矩阵(即 二维数组)。因此给定N个欧几里得空间中的,其距离矩阵就是一个非负实数作为元素的N×N的对称矩阵。这些点两两之间点对的数量,N×(N-1)/2,也就是距离矩阵中独立元素的数量。距离矩阵和邻接矩阵概念相似,其区别在于后者仅包含元素(点)之间是否互相连通,并没有包含元素(点)之间的连通的成本或者距离。因此,距离矩阵可以看成是邻接矩阵的加权形式。
举例来说,我们分析如下二维点a至f。在这里,我们把点所在像素之间的欧几里得度量作为距离度量
生物信息学中,距离矩阵用来表示与坐标系无关的蛋白质结构,还有序列空间中两个序列之间的距离。这些表示被用在结构比对序列比对,还有在核磁共振X射线结晶学中确定蛋白质结构
有时候距离矩阵也被称作相似性矩阵。
系统发生树
系统发生树(英语:phylogenetic tree)又称演化树或进化树(evolutionary tree),是表明被认为具有共同祖先的各物种演化关系的树状图。是一种亲缘分支分类方法(cladogram)。在图中,每个节点代表其各分支的最近共同祖先,而节点间的线段长度对应演化距离(如估计的演化时间)。
树可分为有根树无根树两类。有根树是具有方向的,包含唯一的节点,将其作为树中所有物种的最近共同祖先。最常用的确定树根的方法是使用一个或多个无可争议的同源物种作为外群(英文outgroup),这个外群要足够近,以提供足够的信息,但又不能太近以至于和树中的种类相混。
把有根树去掉根即成为无根树。一棵无根树在没有其他信息(外群)或假设(如假设最大枝长为根)时不能确定其树根。无根树是没有方向的,其中线段的两个演化方向都有可能。
最邻近搜索
最邻近搜索(NearestNeighborSearch, NNS)又称为“最近点搜索”(Closest point search),是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间M中给定一个点集S和一个目标点q∈M,在S中找到距离q最近的点。很多情况下,M为多维的欧几里得空间,距离由欧几里得距离曼哈顿距离决定。
高德纳在《计算机程序设计艺术》(1973)一书的第三章中称之为邮局问题,即居民寻找离自己家最近的邮局。
最邻近搜索问题有若干种解决方案,这些算法的优劣决定于他们求解的时间复杂度和用来查找的数据结构的空间复杂度。一种通常的说法表述为“维数灾难”(curse of dimensionality),指对于在大维数的欧几里得空间里用最邻近搜索的话,无法找到多项式的算法和多对数的查找时间。
参考资料
最新修订时间:2022-10-24 16:39
目录
概述
简介
距离矩阵
参考资料