트리 얼라인먼트

계산 계통학에서 나무 정렬은 DNA, RNA 또는 단백질의 세 개 이상의 배열 또는 여러 배열의 정렬을 생성하는 것과 관련된 계산 문제입니다.염기서열은 계통수로 배열되어 종 또는 분류군 간의 진화적 관계를 모델링합니다.시퀀스 간의 편집 거리는 트리 내의 모든 편집 거리의 합이 최소화되도록 트리의 각 내부 정점에 대해 계산됩니다.트리 정렬은 관리 가능한 트리 크기와 계산 작업 간에 다양한 트레이드오프를 가진 여러 알고리즘 중 하나를 사용하여 수행할 수 있습니다.

정의.

입력: 시퀀스$$ $세트$ S$, S$로 $라벨$이 붙은$$ $계통수$ T$,$ $시퀀스$ 간 거리 편집 $함수$ d$.$

출력: ${\displaystyle {T(\backslash }_{}}$$displaystyle$ T${\displaystyle )}$의 내부 꼭지점 라벨링$displaystyle \Sigma$ _${e\in T(e)})$을 최소화합니다.$여기$서 d$)\displaystyle$ d$(e)$는 e$(\displaystyle$ e$)$의 엔드포인트 사이의 편집 거리입니다.

작업은 NP-hard입니다.^[1]

배경

시퀀스 얼라인먼트

생물정보학에서 정보처리의 기본방법은 배열데이터를 대조하는 것이다.생물학자들은 그것을 생물학적 배열에서 기능, 구조, 그리고 진화 정보를 발견하기 위해 사용한다.계통발생학적 분석, 하플로타입 비교, RNA 구조의 예측 등 다음 분석이 시퀀스 어셈블리를 기반으로 합니다.따라서 시퀀스 정렬의 효율은 이러한 문제를 해결하는 효율에 직접적인 영향을 미칩니다.합리적이고 효율적인 배열 배치를 설계하기 위해, 알고리즘 유도는 생물 정보학 분야에서 중요한 연구 분야가 된다.

일반적으로 시퀀스 얼라인먼트는 문자 추가, 문자 삭제 또는 각 문자열에 대한 공백 추가를 통해 유사성이 가장 큰 여러 문자열에서 문자열을 구성하는 것을 의미합니다.다중 시퀀스 정렬 문제는 일반적으로 쌍별 시퀀스 정렬에 기초하고 있으며, 현재 쌍별 시퀀스 정렬 문제에 대해 생물학자들은 동적 프로그래밍 접근방식을 사용하여 최적의 솔루션을 얻을 수 있다.그러나 다중 배열 정렬 문제는 여전히 생물 정보학에서 가장 어려운 문제 중 하나이다.이는 다중 시퀀스 정렬에 대한 최적 솔루션을 찾는 것이 NP-완전 문제로 입증되었으며 대략적인 최적 솔루션만 ^[2]얻을 수 있기 때문입니다.

거리행렬법

거리법은 문자열 쌍으로 동작할 때 하나의 시퀀스 u를 다른 시퀀스 v로 변환하는 데 필요한 문자 삽입, 삭제 및 치환의 최소 동작 횟수를 측정합니다.편집 거리의 계산은 동적 프로그래밍에 기초할 수 있으며 방정식은 O(u × v) 시간으로, 여기서 u와 v는 u와 ^[3]v의 길이입니다.거리법은 계산생물학의^[4] 기본원칙이기 때문에 편집거리의 효율적인 추정이 필수적이며 유전특성의 함수인 "대칭성"을 사용할 수 있다.편집 거리를 계산하는 데 사용되는 일련의 함수로 인해 함수에 따라 결과가 달라질 수 있습니다.트리 정렬 문제에는 최적의 편집 거리 함수를 찾는 것이 필수적입니다.

트리 정렬의 문제

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2019년 1월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

트리 정렬은 스코어링 모드와 알파벳 크기가 제한되는 NP-하드 문제를 야기합니다.최적화된 솔루션을 찾는 데 사용되는 알고리즘으로 찾을 수 있습니다.그러나 효율과 수열 사이에는 기하급수적인 관계가 있습니다. 즉, 수열의 길이가 매우 클 경우 결과를 얻기 위해 필요한 계산 시간이 엄청나게 길다는 것을 의미합니다.별 정렬을 사용하여 대략적으로 최적화된 솔루션을 얻는 것이 트리 정렬을 사용하는 것보다 빠릅니다.그러나 다중 시퀀스 유사성의 정도가 무엇이든 간에, 별의 정렬의 시간 복잡도는 시퀀스 번호의 제곱 및 시퀀스 평균 길이의 제곱과 비례 관계가 있습니다.통상대로 MSA의 시퀀스는 너무 길기 때문에 비효율적이거나 허용할 수 없습니다.따라서 시간 복잡성을 선형으로 줄이는 문제는 트리 정렬의 핵심 문제 중 하나입니다.

조합 최적화 전략

조합 최적화는 MSA 문제를 해결하기 위한 좋은 전략입니다.조합 최적화 전략의 개념은 다중 시퀀스 정렬을 쌍 시퀀스 정렬로 변환하여 이 문제를 해결하는 것입니다.변환 전략에 따라 조합 최적화 전략은 트리 정렬 알고리즘과 별 정렬 알고리즘으로 나눌 수 있습니다.특정 다중 시퀀스 $세트{\displaystyle }$S(\$displaystyle$ S$)$ =$$ $(\$ ..., $(\$}})$$에 대해 n개의 리프 노드를 가지며 이$진화{\displaystyle }$ $트리$와 세트 S(\$displaystyle$ S$)$ 사이에 일대일 관계를 설정하는 진화 트리를 찾습니다. 내부 시퀀스 할당진화 트리의 ods, 우리는 각 에지의 총 점수를 계산하고, 모든 에지의 점수의 합계는 진화 트리의 점수이다.트리 정렬의 목적은 최대 점수를 얻을 수 있는 할당된 시퀀스를 찾고 진화 트리와 노드의 할당된 시퀀스에서 최종 일치 결과를 얻는 것입니다.별 정렬은 트리 정렬의 특별한 경우로 볼 수 있습니다.별 정렬을 사용할 경우 진화 트리는 내부 노드가 하나이고 리프 노드가 n개뿐입니다.내부 노드에 할당된 시퀀스를 코어 ^[5]시퀀스라고 합니다.

키워드 트리 이론과 Aho-Corasick 검색 알고리즘

조합 최적화 전략을 사용하여 다중 시퀀스 정렬을 쌍 시퀀스 정렬로 변환하면 주요 문제가 "다중 시퀀스 정렬의 효율성을 향상시키는 방법"에서 "쌍별 시퀀스 정렬의 효율성을 향상시키는 방법"으로 변경됩니다.키워드 트리 이론과 Aho-Corasick 검색 알고리즘은 쌍별 시퀀스 정렬 문제를 해결하기 위한 효율적인 접근법이다.키워드 트리 이론과 Aho-Corasick 검색 알고리즘을 조합하는 목적은 다음과 같은 문제를 해결하는 것입니다.특정 긴 $문자열{\displaystyle }$T(\$displaystyle$ T$$$)$와 짧은 $P$(\$displaystyle$ P$)$ =$$ { p$$ { $displaystyle p_$1}, ${\displaystyle {p\mathrm{}}_{}}$2 {\$displaystyle$p_${2$}},$$ ..., ${\displaystyle {}_{}}$ {\$displaystyle P_nz$,z>1)에서 $모든{\displaystyle {}_{}}$ $(\$$displaystyle$ $P_{i$})의$$ 위치를 T$(\displaystyle$ T$)$에서 $찾습니다{\displaystyle }$.$세트{\displaystyle }$P(\$displaystyle$ P$)$에서 생성된 키워드 트리가 사용되며, 이 키워드 트리와 함께 T$(\displaystyle$ T$)$에서 Aho-Corasick 검색 알고리즘을 ^[6]통해 검색됩니다.이 방법을 사용하여 T에서 $모든{\displaystyle {}_{}}$ $(\$의 위치를 찾는 데 걸리는 총 시간은 O$(m\displaystyle$${\displaystyle }$)$$+ n(\$displaystyle$${\displaystyle }$)$$+ k(\$displaystyle$ k$)$$$입니다. $여기$서$$m\$displaystyle$m $=$ $T{\displaystyle }$$(T\displaystyle$Tyle N$)$의 길이$)$입니다.$($ 스타일 $P_{i$})($$$모든{\displaystyle {}_{}}$ $($ P_${i$와 k$(스타일$ k$)$의 합)는 T ${{display$ $스타일{\displaystyle }$ T$\}$에서$$모든 $Pi(디스플레이$ 스타일$P_{$i$$})의 발생 합계를 의미합니다.

키워드 트리 이론

$세트{\displaystyle }$P {\$displaystyle$ P$$=$$ { ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$\ $displaystyle p_{1}$, ${\displaystyle {p\mathrm{}}_{}}$2 \ $displaystyle p_{2}$ , ...$$ , ${\displaystyle {}_{}}$ ${\displaystyle z_{}}$ \$displaystyle p_{z}$ }$$ (z4N,z>1) 키워드 트리는 루트 트리로, 이 키워드 트리는 다음과 같습니다.

(1): 각 가장자리는 한 글자를 명확하게 구분합니다.

(2) 동일 노드로부터 분리된 2개의 에지는 다른 문자에 대응한다.

(3) 각 $패턴{\displaystyle {}_{}}$ ${\displaystyle {Pi}_{}}${\$display P_{i$}($$i=1,2,...z)는 $노드{\displaystyle }$v {\$displaystyle$ v$\}$에 대응하며 루트 K에서 $노드{\displaystyle }$v {\$displaystyle$ v$}$까지의 경로는 $문자열{\displaystyle {}_{}}$ ${\displaystyle {Pi}_{}}${\$displaystyle P_{i$의 철자를 정확하게 입력할 수 있습니다.

이 K 트리의 각 리프 노드에 대해 $세트{\displaystyle }$P의 특정 패턴 중 하나에 해당합니다(\ $displaystyle P$

${\displaystyle L}$( ${\displaystyle v}$)$$\ $displaystyle$L ($v$ )는$$ 루트노드에서 $노드{\displaystyle }$v \ $displaystyle$ v$$에 접속되어 있는 STRING 을 나타내기 위해서 사용됩니다.${\displaystyle 그}$후 ${\displaystyle \mathrm{Lp}}$ v )\ $displaystyle Lp$ ( v $)$는 가장$$ 긴 서픽스의 길이를 나타내기 위해서 사용됩니다(또, 이 서픽스는 $세트{\displaystyle }$ P$\$ $displaystyle$P 의 패턴 중 하나의 프리픽스입니다).$$키워드 트리의 루트노드에서 이 프레픽스를 검색하고 검색이 ^{[clarification needed][7]}종료되었을 때 n ${\displaystyle v_{}}$ {\$displaystyle n_{$v$$$}$ 로 $표시$되는 마지막 노드를 검색합니다.

예를 들어$,$ P\$style$P={$$$too{\displaystyle }$, tatoo, theater, other} 집합과 키워드 트리가 오른쪽에 표시됩니다.이 예에서 ${\displaystyle L}$(${\displaystyle }$v$$) \ $displaystyle Lp$( v ) $=$ $potat$일 ${\displaystyle \mathrm{경우}}$L ${\displaystyle p}$($$v ) \ $displaystyle Lp$ ($$v ) $=$ tat = 3 이며 $노드{\displaystyle }$v \ $displaystyle$v }의$$ 장애 링크를 그림에 나타냅니다.

Aho-Corasick 알고리즘의 시간 복잡성을 개선하기 위해서는 장애 링크를 확립하는 것이 중요합니다.원래 다항식 시간을 검색을 위한 선형 시간으로 줄이는 데 사용할 수 있습니다.따라서 키워드 트리 이론의 핵심은 키워드 트리의 모든 장애 링크($모든{\displaystyle {}_{}}$ ${\displaystyle {n개}_{}}$의 \$displaystyle n_{v}$를 선형 시간 내에 찾는 것을 의미함)를 찾는 것입니다.루트 노드로부터의 거리가 k$({displaystyle$ k$\}$ $이하$인 모든 $노드{\displaystyle }$v\$displaystyle$ v\$displaystyle$ v$\}$의 ${\displaystyle {n개}_{}}$ v$\$v}$개$를 찾을 수 있다고 가정합니다.그런 다음 루트 노드로부터의 $거리가$k $+$ 1인 $v의$${\displaystyle n_{}}$ $v${\$displaystyle$ n_$$${$$$$v}$를 $구할{\displaystyle {}_{}}$ 수 있습니다.부모 노드는 $v{\displaystyle {}^{}}$ {$displaystyle$ v$\},$ 노드$v{\displaystyle }$ {\$displaystyle$v$$} $및{\displaystyle {}^{}}$ v ${\$ v$\text{'}\}$로 표시되는 $문자$는$$x {\$displaystyle$ x$\}$입니다.

(1): 노드 ${\displaystyle n_{}^{}}$ v ${\$ { $displaystyle n$_ { $v$}의 다음$$ 문자가$$x { $displaystyle$ x$$}인 경우 이 에지의 다른 노드는 $w{\displaystyle }${ $displaystyle$ w$\},$ ${\displaystyle n_{}}$ v {$displaystyle n_{v}$ $=$ ${\displaystyle }$ { $displaystyle$w$\}$ 로 설정할 수 있습니다.

(2): n ${\displaystyle v_{}^{}}$ ${\$ { $displaystyle$ n$_$ { $v$} because$$ $nodes{\displaystyle {}_{}^{}}$ because because because because because because because because because because because $because{\displaystyle }$$$、 L${\displaystyle }$（ n _ { v$$$）$ 、 $x$$displaystyle$ X$\}$의 서픽스와 $일치$하기 때문에 L ( ${\displaystyle {}_{}^{}}$${\displaystyle {}_{}}$${\displaystyle v_{}^{}}$$$) { $displaystyle$L ( n _ ${ v$ )${\displaystyle }$}의$$ 서픽스입니다.루트 노드(프리픽스와 유사), ${\displaystyle n_{}^{}}$ v ${\$ { $displaystyle n$_ { $v$} $n$ 뒤의$x{\displaystyle }$ { $displaystyle$ x$$} 를$$ 검출할 수 있습니다.그렇지 않으면 x$\displaystyle$ x$\$ 또는$$ 루트 노드가 발견될 $때$까지 이 프로세스를 계속할 수 있습니다.

아호-코라식 검색 알고리즘

키워드 트리에서 모든 장애 링크를 확립한 후 Aho-Corasick 검색 알고리즘을 사용하여 선형 시간 내에 $모든{\displaystyle {}_{}}$ $(\$ P_${i$})($$i=1,2,...z)의 위치를 찾습니다.이 단계에서 시간 복잡도는 O(m+k)입니다.

기타 전략

MSA, DNA, RNA 및 단백질에서는 보통 배열이 생성되며 이들은 진화적 관계를 갖는 것으로 가정된다.진화 계열의 RNA, DNA, 배열의 생성된 지도를 비교함으로써, 사람들은 단백질의 보존을 평가할 수 있고 진화 계열 간의 차이를 비교함으로써 기능적인 유전자 영역을 찾을 수 있다.일반적으로 여러 시퀀스 정렬 문제를 해결하기 위해 휴리스틱 알고리즘과 트리 정렬 그래프도 채택된다.

휴리스틱 알고리즘

일반적으로 휴리스틱 알고리즘은 반복적인 전략에 의존하며, 즉 비교 방법에 기초하여 반복적인 프로세스에 의한 다중 시퀀스 정렬의 결과를 최적화한다.Davie M.은 다중 시퀀스 정렬 문제를 해결하기 위해 입자 군집 최적화 알고리즘을 사용할 것을 제안했다.이케다 다카히로는 A* 검색 알고리즘에 기초한 휴리스틱 알고리즘을 제안했다.E. Birney는 최초로 숨겨진 마르코프 모델을 사용하여 다중 시퀀스 정렬 문제를 해결하자고 제안했고, 다른 많은 생물학자들은 유전 알고리즘을 사용하여 이를 ^[8][9]해결했다.이러한 알고리즘은 일반적으로 견고하고 시퀀스 수에 민감하지 않지만 단점도 있습니다.예를 들어 입자군 최적화 알고리즘의 결과는 불안정하고 그 장점은 난수 선택에 달려 있으며, A* 검색 알고리즘의 실행 시간이 너무 길며, 유전 알고리즘이 ^{[clarification needed]}국소적으로 우수한 알고리즘으로 분류되기 쉽습니다.

트리 정렬 그래프

대략적으로 트리 정렬 그래프는 트리를 그래프로 정렬하고 최종적으로 그것들을 합성하여 통계를 개발하는 것을 목표로 합니다.생물학에서, 나무 정렬 그래프(TAG)는 나무 집합에서 진화적 충돌 또는 중복 분류군을 제거하기 위해 사용되며, 불확실성과 충돌을 탐색하기 위해 쿼리될 수 있다.정렬, 합성 및 분석 방법을 통합함으로써, TAG는 광범위한 시퀀스로부터 얻은 충돌 관계와 부분 중복 분류군을 해결하는 것을 목표로 한다.또한, 트리 정렬 그래프는 ^[10]Berry에 의해 슈퍼 트리 구성 테스트를 성공적으로 마친 슈퍼 트리 및 이식 운동에 대한 기본 접근법 역할을 합니다.트리에서 그래프로의 변환에는 소스 트리에서 유사한 노드와 가장자리가 포함되므로 TAG는 추가 분석을 위해 원본 소스 트리를 추출할 수도 있습니다.TAG는 정렬 트리 세트를 조합한 것입니다.상충되는 가설의 진화적 관계를 저장하고 진화적 가설을 발전시키기 위해 근원수를 합성할 수 있다.따라서, 이것은 다른 ^[11]정렬 문제를 해결하기 위한 기본적인 방법입니다.

「 」를 참조해 주세요.

• 범용 트리 얼라인먼트

레퍼런스