近邻结合法,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),指对于在大维数的欧几里得空间里用最邻近搜索的话,无法找到多项式的算法和多对数的查找时间。