계통 발생의 최소 제곱 추론

계통발생학에서의 최소제곱추론은 쌍방향 유전거리의 관측행렬과 선택적으로 무게행렬에 기초한 계통발생학적 트리를 생성한다.목표는 거리 제약을 최대한 충족하는 트리를 찾는 것입니다.

일반 및 가중 최소 제곱

관찰된 쌍방향 $거리{\displaystyle {}_{}}$ $($와 계통수 $($ $사이$의 거리(즉, $잎{\displaystyle }$i(\$displaystyle$ i$)$에서 $잎{\displaystyle }$j(\$displaystyle$ j$)$까지의 경로의 분기 길이의 합)는 다음과 같이 측정된다.

$({displaystyle S=\sum _{ij}w_{ij}(D_{ij}-T_{ij})^{2})$

여기서 $\$의 $가중치$는 사용되는 최소 제곱법에 따라 달라집니다.최소 제곱 거리 트리 구성은 S가 최소인 트리(토폴로지 및 분기 길이)를 찾는 것을 목적으로 합니다.이것은 사소한 문제가 아닙니다.이는 잎의 수가 기하급수적인 크기가 있는 루트되지 않은 이진수 트리 토폴로지의 이산 공간을 검색하는 것을 포함한다.n개의 잎에 대해 1 • 3 • 5 • ... (2n-3)개의 다른 토폴로지가 있다.소수의 잎에 대해서는 이미 열거할 수 없습니다.휴리스틱 검색 방법은 상당히 양호한 토폴로지를 찾는 데 사용됩니다.특정 위상에 대한 S 평가(분기 길이 계산 포함)는 선형 최소 제곱 문제입니다.오차${\displaystyle }$제곱(${\displaystyle {\mathrm{Di}}_{}}$j - ${\displaystyle T_{}}$ i${\displaystyle {}_{}{}^{}{j}_{}}$ ) $($2$\})$에는 관측된 거리의 변화에 대한 지식과 가정에 따라 몇 가지 가중치가 부여됩니다.오류에 대해 아무것도 알려지지 않은 경우 또는 오류가 독립적으로 분포되어 관측된 모든 거리에 대해 동일하다고 가정할 경우 모든 $가중치{\displaystyle {}_{}}$ $w_{ij}$는 1로 설정됩니다.그러면 정규 최소 제곱 추정치가 나옵니다.가중 최소 제곱의 경우 오차는 독립적이라고 가정한다(또는 상관관계를 알 수 없다).독립 오차가 주어진 경우, 특정 가중치는 해당 거리 추정치의 분산의 역수로 이상적으로 설정되어야 한다.때로는 분산을 알 수 없지만 거리 추정치의 함수로 모형화할 수 있습니다.예를 들어, Fitch 및 Margoliash 방법에서는 분산이 거리 제곱에 비례한다고 가정합니다.

일반화 최소 제곱

위에서 설명한 정규 및 가중 최소 제곱 방법은 독립적인 거리 추정치를 가정한다.거리가 게놈 데이터에서 도출되면 (진정한 나무의) 내부 가지에서 일어나는 진화적 사건이 동시에 여러 거리를 위아래로 밀어 올릴 수 있기 때문에 이들의 추정치는 동일하다.결과 공분산은 일반화 최소 제곱법, 즉 다음 양을 최소화하는 방법을 사용하여 고려할 수 있다.

$\sum _{ij,kl}w_{ij,kl}(D_{ij}-T_{ij})(D_{kl}-T_{kl})$

${\displaystyle {여기}_{}}$서 w ${\displaystyle i_{}}$j , ${\displaystyle k_{}}$l {$displaystyle w_{ij,}}}}$은 거리 추정치의 공분산 행렬의 역수 항목입니다.

계산의 복잡성

최소 제곱 잔차를 최소화하는 트리 및 가지 길이를 찾는 것은 NP-완전 문제입니다.^[2]단, 주어진 트리에 대해 최적의 분기 길이는 일반 최소 제곱의 경우${\displaystyle }$O ($n$ 2$)$ {$displaystyle{\displaystyle }$O (n^{2}) 시간, 가중 ${\displaystyle {}^{}}$ 제곱의 $경우$ O (${\displaystyle {n\mathrm{}}^{}}$ $3{\displaystyle }$$)$ {$displaystyle$O ($n^{3})$ 시간$$, $최소{\displaystyle }$ 제곱의 경우 O${\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$ 4$)$ {$displaystyle$O ($n^{4})$ 시간으로$$$$ 결정될 수 있다.분산 행렬).^[3]

외부 링크

• PHYLIP, 가중 최소 제곱법의 구현을 포함하는 자유롭게 분산된 계통학적 분석 패키지
• PAUP, 구매 가능한 유사한 패키지
• Darwin은 통계, 숫자, 배열 및 계통 분석을 위한 함수 라이브러리를 갖춘 프로그래밍 환경입니다.

레퍼런스