近鄰結合法

近鄰結合法，neighbor-joining method，套用領域演化生物學。

基本介紹

• 中文名：近鄰結合法
• 外文名：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），指對於在大維數的歐幾里得空間裡用最鄰近搜尋的話，無法找到多項式的算法和多對數的查找時間。