무정렬 시퀀스 분석

생물정보학에서 분자 시퀀스 및 구조 데이터에 대한 정렬 없는 시퀀스 분석 접근방식은 정렬 기반 접근방식보다 대안을 제공한다.^[1]null

생물학적 연구를 통해 생성되는 다양한 유형의 데이터를 분석해야 하는 등장과 필요성이 생물정보학 분야에 대두되고 있다.^[2]DNA, RNA 및 단백질, 유전자 표현 프로파일 또는 미세배열 데이터, 대사 경로 데이터는 생물정보학에서 분석되는 주요 데이터 유형 중 일부다.그중에서도 차세대 시퀀싱 기술의 도래로 시퀀스 데이터가 기하급수적으로 증가하고 있다.생물정보학의 기원 이후, 시퀀스 분석은 데이터베이스 검색, 게놈 주석, 비교 유전체학, 분자 유전체학, 유전자 예측에서 광범위한 응용을 가진 연구의 주요 영역으로 남아있다.시퀀스 분석을 위한 선구적 접근방식은 글로벌 또는 로컬, 쌍 또는 다중 시퀀스 정렬 중 하나의 시퀀스 정렬에 기초하였다.^[3][4]정렬 기반 접근방식은 일반적으로 연구 중인 시퀀스가 밀접하게 연관되어 있고 신뢰성 있게 정렬될 수 있을 때 우수한 결과를 제공하지만, 시퀀스가 서로 다른 경우에는 신뢰할 수 있는 정렬을 얻을 수 없으므로 시퀀스 정렬의 적용이 제한된다.정렬 기반 접근법의 또 다른 제한사항은 계산 복잡성이며, 따라서 대규모 시퀀스 데이터를 처리할 때 시간이 많이 소요된다는 것이다.^[5]차세대 시퀀싱 기술의 등장으로 방대한 시퀀싱 데이터가 생성되었다.이 시퀀스 데이터의 크기는 조립, 주석 및 비교 연구에서의 정렬 기반 알고리즘에 문제를 제기한다.null

정렬이 필요 없는 방법

정렬이 없는 방법은 크게 a) k-mer/word 주파수 기반 방법, b) 공통 서브스트링 길이에 기반한 방법, c) 단어 일치(간격) 횟수에 기반한 방법, d) 방법, 정보이론에 기반한 방법, f) 방법 등 5가지 범주로 분류할 수 있다.정렬되지 않은 접근방식은 시퀀스 유사성 검색,^[6] 군집화 및 시퀀스 분류에 사용되었으며,^[7] 최근에는 계통유전학(Phylogenetics^[8][9])에 사용되었다(그림 1).null

정렬이 필요 없는 접근방식을 채택한 그러한 분자 계통 분석은 차세대 계통학(Phylogenomics)의 일부라고 한다.^[9]다수의 검토 기사에서 시퀀스 분석에서 정렬되지 않은 방법에 대한 심층적인 검토를 제공한다.^{[1][10][11][12][13][14][15]}null

AF프로젝트는 무정렬 시퀀스 비교를 위한 소프트웨어 도구를 벤치마킹하고 비교하기 위한 국제적인 협력이다.^[16]null

k-mer/word 주파수 기반 방법

k-mer/word 주파수를 기반으로 하는 일반적인 방법으로는 피쳐 주파수 프로파일(^[17][18]FFP), 컴포지션 벡터(^[19][20]CV), 복귀 시간 분배(RTD),^[21] 주파수 혼돈 게임 표현(FCGR),^[22] 스페이스 워드가 있다.^[23]null

피쳐 주파수 프로파일(FFP)

FFP 기반 방법에 관련된 방법론은 각 가능한 k-mer(핵산염 순서에 대한 k-mer의 가능한 수:4^k, 단백질 순서:20^k)의 수를 계산하는 것으로 시작한다.각 시퀀스의 각 k-mer 카운트는 그 시퀀스의 모든 k-mer 카운트의 총계로 나누어 정규화된다.이는 각 시퀀스를 형상 주파수 프로파일로 변환하도록 이끈다.그런 다음 두 시퀀스 사이의 쌍 현명한 거리는 각각의 FFP 사이의 Jensen-Shannon(JS) 차이를 계산한다.따라서 얻은 거리 행렬은 인접 결합, UPGMA 등과 같은 클러스터링 알고리즘을 사용하여 계통 생성 트리를 구성하는 데 사용할 수 있다.null

구성 벡터(CV)

이 방법에서는 주어진 시퀀스에서 가능한 각 k-mer의 출현 빈도를 계산한다.이 방법의 다음 특징 단계는 선택적 진화의 역할을 강조하기 위해 무작위 중립 돌연변이의 영향을 줄이기 위해 마르코프 모델을 사용하여 이러한 주파수의 무작위 배경의 뺄셈이다.정규화된 주파수는 주어진 시퀀스의 구성 벡터(CV)를 형성하기 위해 고정된 순서로 배치된다.그런 다음 코사인 거리 함수를 사용하여 시퀀스의 CV 간 쌍별 거리를 계산한다.따라서 얻은 거리 행렬은 인접 결합, UPGMA 등과 같은 클러스터링 알고리즘을 사용하여 계통 생성 트리를 구성하는 데 사용할 수 있다.이 방법은 합성 벡터 계산에 포함되는 효율적인 패턴 매칭 알고리즘에 의존하여 확장할 수 있다: (i) k 값에 대한 모든 k-mer, (ii) 임의로 설정된 최대 k 값까지의 모든 길이의 모든 기수, (iii) 모든 최대 기수, (iiii) 어떤 문자 woul로 확장된 경우 하위 문자열이 최대인 경우발생 횟수의 감소를 야기한다.^[24][25]null

복귀시간분배(RTD)

RTD 기반 방법은 시퀀스에서 k-mer의 개수를 계산하지 않고, 대신 k-mer의 재등장에 필요한 시간을 계산한다.시간은 특정 k-mer가 연속적으로 나타나는 잔류물의 수를 가리킨다.따라서 순차적으로 각 k-mer의 발생은 RTD의 형태로 계산되며, RTD는 두 개의 통계적 매개변수 평균(μ)과 표준 편차(μ)를 사용하여 요약된다.따라서 각 시퀀스는 4^k RTD의 μs와 μs를 포함하는 크기 2 24의^k 숫자 벡터 형태로 표현된다.시퀀스 간 쌍 지혜 거리는 유클리드 거리 측정을 사용하여 계산한다.따라서 얻은 거리 행렬은 인접 결합, UPGMA 등과 같은 클러스터링 알고리즘을 사용하여 계통 생성 트리를 구성하는 데 사용할 수 있다.엔트로피 검색을 통한 최근 접근 패턴 추출(PEER)은 k-mer 길이를 직접 검출하고 엔트로피를 사용하여 발생 간격을 요약한다.null

주파수 혼돈 게임 표현(FCGR)

FCGR 방법은 게놈 시퀀스에 대해 스케일 독립적 표현을 제공하는 CGR(Cause Game Presentation) 기법에서 발전했다.^[26]CGR은 각 격자 사각형이 시퀀스에서 특정 길이의 올리고뉴클레오티드 발생을 나타내는 격자선으로 나눌 수 있다.이러한 CGR의 표현은 주파수 혼돈 게임 표현(FCGR)이라고 불린다.이는 각 시퀀스를 FCGR로 표현하도록 이끈다.시퀀스의 FCGR 간 쌍 지혜 거리는 피어슨 거리, 해밍 거리 또는 유클리드 거리를 사용하여 계산할 수 있다.^[27]null

스페이스 워드 주파수

대부분의 정렬되지 않은 알고리즘이 시퀀스의 단어 구성을 비교하는 반면, 스페이스 워드는 주의의 패턴을 사용하고 위치에는 상관하지 않는다.그런 다음 연속적으로 간격 있는 단어가 나타나는 것은 매치 위치의 문자에 의해서만 정의되며, 상관 없음 위치의 문자는 무시된다.입력 시퀀스에서 연속적인 단어의 빈도를 비교하는 대신에, 이 접근법은 미리 정의된 패턴에 따라 간격 있는 단어의 빈도를 비교한다.^[23]사전 정의된 패턴은 일치 횟수의 분산,^[28] 여러 모델에서 처음 발생할 확률 ^[29]또는 예상 단어 빈도와 실제 선형 거리 사이의 Pearson 상관 계수를 분석하여 선택할 수 있다.^[30]null

공통 기호의 길이에 따른 방법

이 범주의 방법은 시퀀스 쌍에 있는 하위 문자열의 유사성과 차이를 사용한다.이 알고리즘들은 주로 컴퓨터 과학에서 문자열 처리에 사용되었다.^[31]null

평균 공통 하위 문자열(ACS)

이 접근법에서, 선택된 시퀀스 쌍(각각 길이 n과 m의 A와 B)에 대해, 어떤 위치에서 시작하는 가장 긴 하위 문자열은 어떤 위치에서 다른 시퀀스 (B)와 정확히 일치하는 하나의 시퀀스 (A)로 식별된다.이러한 방식으로 시퀀스 A의 서로 다른 위치에서 시작하여 시퀀스 B의 일부 위치에서 정확히 일치하는 최장 기하의 길이를 계산한다.이 모든 길이의 평균은 $측정값{\displaystyle }$ L ${\displaystyle (A}$, B$){\displaystyle$ L $(A,B)}$을 도출하기 위해 산출된다$.$ 직관적으로 L${\displaystyle }$($){\displaystyle$L ($A,B)}$이 클수록 두 시퀀스는 더 유사하다$.$시퀀스 길이의 차이를 설명하기 위해 $L{\displaystyle }$( A${\displaystyle }$, ${\displaystyle B}$) ${\displaystyle L(A,B)}$을(를) 정규화 [즉, ${\displaystyle L}$( A${\displaystyle }$, B${\displaystyle }$)${\displaystyle }$/ ${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle m}$) ${\displaystyle L(A,B)/\log(m)}].$이것은 시퀀스 사이의 유사성 측도를 제공한다.null

거리 측정을 도출하기 위해 유사성 측정의 역치를 취하고, $d{\displaystyle }$ (${\displaystyle A}$, $){\displaystyle d(A,A)}$가 0이 되도록$$ 보정 항을 뺀다.그러므로

${\displaystyle d(A,B)=\left[{\frac {\log m}{L(A,B)}}}}\rift[{\frac {\log n}{L(A,A)}}}}\right].}$

This measure ${\displaystyle d(A,B)}$ is not symmetric, so one has to compute ${\displaystyle d_{s}(A,B)=d_{s}(B,A)=(d(A,B)+d(B,A))/2}$, which gives final ACS measure between the two strings (A and B).^[32]접미사 트리를 사용하여 반복/하위 검색을 효율적으로 수행할 수 있다.^[33][34][35]null

k-평균 공통 하위 문자열 접근법(kmacs)

이 접근방식은 ACS 접근방식의 일반화다.두 개의 DNA 또는 단백질 시퀀스 사이의 거리를 정의하기 위해 kmacs는 첫 번째 시퀀스의 각 위치 i에 대해 i에서 시작하여 두 번째 시퀀스의 하위 문자열과 최대 k matches를 일치시키는 것으로 추정한다.이 값들의 평균을 시퀀스 사이의 유사성 측정으로 정의하고 이를 대칭 거리 측정으로 변환한다.Kmacs는 정확한 k-mismatch 하위 문자열을 계산하지 않는데, 이는 계산 비용이 너무 많이 들지만 그러한 하위 문자열에 근사치가 있기 때문이다.^[36]null

돌연변이 거리(Kr)

이 접근방식은 최단 부존변위(shustring)를 사용하여 두 DNA 시퀀스 사이의 사이트당 대체 횟수를 계산하는 ACS와 밀접하게 관련되어 있다.^[37]null

k-mismatch 공통 기호의 길이 분포

이 접근방식은 프로그램 kmacs를^[36] 사용하여 DNA 시퀀스 쌍에 대해 최대 k개의 불일치가 있는 가장 긴 공통 서브스트링을 계산한다.그런 다음 시퀀스 사이의 계통 생성 거리는 k-mismatch 공통 서브스트링의 길이 분포의 국소 최대값에서 추정할 수 있다.^[38]null

단어 일치(공백) 수에 따른 방법

${\displaystyle D_{}^{}}$ ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ 및$$ $D{\displaystyle {}_{}^{}}$ ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$

이러한 승인자는 두 ${\displaystyle {시퀀스\mathrm{}}_{}}$ 사이의 $k{\displaystyle }$ {\$displaystyle$ k$}$ -mer$$ 일치 수를 카운트하는 $D{\displaystyle {}_{}}$ 2 ${\displaystyle D_$${$2}}$개$의 통계 변형이다$$.비교 시퀀스의 배경 분포를 고려하여 간단한 ${\displaystyle {D\mathrm{}}_{}}$ 2 ${\$2}}개의 $통계$를 개선한다.^[39]null

매시

이것은 두 개의 입력 $시퀀스{\displaystyle }$ 중$$k {\$displaystyle$ k$}$ -mer의$$ 다중 집합에 대한 Jaccard 지수를 추정하기 위해 MinHash bottheet sketch 전략을 사용하는 매우 빠른 방법이다.즉, 시퀀스의 총${\displaystyle }$$$k {\$displaystyle$ k$$} -mer$$ 수와 일치하는 k ${\displaystyle k}$ -mer의 비율을 추정한다.이것은 차례로 비교된 시퀀스 사이의 진화 거리를 추정하는데 사용될 수 있으며, 시퀀스가 마지막 공통 조상으로부터 진화한 이후 시퀀스 위치당 대체 횟수로 측정된다.^[40]null

경사-트리

$이{\displaystyle }$ 접근방식은 k ${\displaystyle k}$ -mer$$ 일치 횟수의 감소를$$ 기반으로 두 단백질 시퀀스 사이의 거리 값을 계산한다.^[41]null

경사-스파M

이 방법은 $기본{\displaystyle }$ 패턴에 있는$$ 일치 $위치{\displaystyle }$ k$$${\displaystyle k$$}$ -mer$$ 또는 spaced-word 일치(SpaM)의$$ $숫자{\displaystyle {}_{}}$ k {\$displaystyle$ $N_{k}$를 각각 다른 값으로 계산한다.$N{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$에 의존하는$$ 부선형 함수 F ${\displaystyle F}$의 기울기는 입력 시퀀스 사이의 Jukes-Canter 거리를 추정하기 위해 계산된다$$.^[42]

스크머

Skmer는 조립되지 않은 시퀀싱 읽기로부터 종 사이의 거리를 계산한다.MASH와 마찬가지로 입력 $시퀀스$에서 k ${\displaystyle k}$ -mer$$ 집합에 Jaccard 인덱스를 사용한다.MASH와는 대조적으로 이 프로그램은 낮은 시퀀싱 커버리지에 대해 여전히 정확하기 때문에 게놈 스키밍에 사용할 수 있다.^[43]null

미세조정에 기초한 방법

엄밀히 말하면, 이 방법들은 정렬이 자유롭지 않다.그들은 미리 정의된 특정 위치에서 일치시키기 위해 시퀀스가 필요한 단순한 갭 프리 마이크로 얼라인먼트를 사용하고 있다.불일치가 허용되는 미세 조정의 나머지 위치에서 정렬된 위치는 계통 추론에 사용된다.null

코필로그

이 방법은 두 시퀀스에서 한 위치 떨어져 있는 두 DNA 시퀀스 사이의 k-mer 일치 쌍으로 정의되는 소위 구조를 검색한다.두 k-mer 일치를 컨텍스트라고 하고, 그 사이의 위치를 오브젝트라고 한다.그런 다음 코-필로그는 물체의 두 뉴클레오티드가 다른 구조물의 분율을 두 시퀀스 사이의 거리를 정의한다.이 접근방식은 조립되지 않은 시퀀싱 읽기에 적용할 수 있다.^[44]null

그리고 나는.

Andi는 가장 정확한 단어 일치가 옆면에 있는 절단되지 않은 국소 선형에 기초하여 유전체 배열 사이의 유전체학적 거리를 추정한다.이러한 단어 일치는 접미사 배열을 사용하여 효율적으로 찾을 수 있다.정확한 단어 일치 간의 갭프리 정렬은 게놈 배열 사이의 유전체학적 거리를 추정하는 데 사용된다.결과 거리 추정치는 직위당 최대 약 0.6개의 대체에 대해 정확하다.^[45]null

필터링된 공백 단어 일치(FSWM)

FSWM은 이른바 매치 포지션과 관리하지 않는 포지션을 나타내는 사전 정의된 이진 패턴 P를 사용한다.입력 DNA 시퀀스 쌍의 경우 간격-단어 일치, 즉 P의 일치 위치에서 일치하는 뉴클레오티드와 일치하는 국소 간격-자유 맞춤 및 치료하지 않는 위치에서의 불일치 가능성을 검색한다.가짜 저점수 간격 단어 일치는 폐기되며, 입력 순서 사이의 진화 거리는 나머지 동음이의 간격 단어 일치의 관리 안 함 위치에서 서로 정렬된 뉴클레오티드를 기반으로 추정한다.^[46]FSWM은 조립되지 않은 NGS 읽기를 기반으로 거리를 추정하도록 조정되었으며, 이 프로그램의 버전은 Read-SpaM이라고 불린다.^[47]null

프로토스파엠

Prot-SpaM(Proteom 기반 Spaced-word Matchs)은 부분 또는 전체 프로테오메 시퀀스에 대한 FSWM 알고리즘의 구현이다.^[48]null

멀티스파엠

Multi-SpaM(MultipleSpaced-word Matchs)은 FSWM 아이디어를 다중 시퀀스 비교로 확장하는 게놈 기반 유전체 재구성에 대한 접근법이다.^[49]매치 포지션과 비케어 포지션의 바이너리 패턴 P를 감안하여 P-블록, 즉 P의 매치 포지션에서 일치하는 뉴클레오티드와 일치하는 국소 갭프리 4방향 얼라인먼트를 검색하고, 비케어 포지션에서 불일치 가능성을 검색한다.이러한 4방향 맞춤은 입력 게놈 시퀀스 집합에서 랜덤하게 샘플링된다.각 P-block에 대해 RAxML을 사용하여 뿌리 없는 트리 토폴로지를 계산한다.^[50] 그런 다음 이들 트리에서 슈퍼 트리를 계산하는 데 4중주 MaxCut 프로그램을 사용한다.null

정보이론에 근거한 방법

정보이론은 무정렬 시퀀스 분석과 비교를 위한 성공적인 방법을 제공했다.기존의 정보이론의 적용은 DNA, RNA, 단백질의 글로벌 및 국소적 특성화, 모티프 및 지역 분류에 대한 게놈 엔트로피 추정 등이다.유전자 지도화, 차세대 염기서열 분석, 메타게노믹스 분야도 유망하다.^[51]null

기준-기준 상관 관계(BBC)

베이스-베이스 상관관계(BBC)는 다음 방정식을 사용하여 게놈 시퀀스를 고유한 16차원 숫자 벡터로 변환한다.

${\displaystyle T_{ij}(K)=\sum _{\ell =1}^{K_{ij}(\ell )\cdot \log_{2}\왼쪽({\frac {P_{ij}(\ell )}{P_{i}}}}}}\오른쪽)$

$P{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$와 $P{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$는 게놈에서 염기 i와 j의 확률을 나타낸다$$.$P{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ (${\displaystyle \ell }$ ) ${\displaystyle P_{ij}(\ell )}$은 게놈의 거리 ℓ에서 base i와 j의 확률을 나타낸다$$.파라미터 K는 베이스 i와 j 사이의 최대 거리를 나타낸다.16개 매개변수 값의 변동은 게놈 함량과 길이의 변동을 반영한다.^[52][53][54]null

정보 상관 관계 및 부분 정보 상관 관계(IC-PIC)

IC-PIC(정보상관 및 부분정보상관) 기반 방법은 DNA 염기상관 특성을 채용한다.IC와 PIC는 다음 공식을 사용하여 계산되었다.

${\displaystyle IC_{\ell }=-2\sum _{i}\log _{2}P_{i}+\sum _{ij}P_{ij}(\ell )\log _{2}P_{ij}(\ell )}$

${\displaystyle PIC_{ij}(\ell )=(P_{ij}(\ell )-P_{i}P_{j}(\ell )^{2}}$

최종 벡터는 다음과 같이 얻는다.

$V={\displaystyle V={IC_{\ell } \over PIC_{ij}(\ell )}{\text{{}{{\ell _{0},\ell _{0}+1,\ldots ,\ell _{0}+n\right\}}}}}}$

베이스 사이의 거리 범위를 규정한다.^[55]null

시퀀스 간 쌍방향 거리는 유클리드 거리 측정을 사용하여 계산한다.따라서 얻은 거리 행렬은 인접 결합, UPGMA 등과 같은 클러스터링 알고리즘을 사용하여 계통생성 트리를 구성하는 데 사용할 수 있다.null

압축

예를 들어 Lempel-Ziv 복잡성과 같은 Kolmogorov 복잡성에 대한 효과적인 근사치를 예로 들 수 있다.일반적인 압축 기반 방법은 시퀀스 간의 상호 정보를 사용한다.이것은 조건부 Kolmogorov 복잡성, 즉 다른 문자열의 사전 지식이 주어진 경우 문자열을 생성하는 데 필요한 최단 자기 증식 프로그램의 길이로 표현된다.이 조치는 k-words를 시퀀스 생성에 쉽게 사용할 수 있기 때문에 시퀀스 측정과 관련이 있다.그것은 때때로 계산적으로 집약적인 방법이다.콜모고로프 복잡성 접근법의 이론적 근거는 베넷, 개스, 리, 비타니, 주렉(1998)이 정보 거리를 제안하여 제시하였다.^[56]Kolmogorov 복잡성은 계산할 수 없는 압축 알고리즘에 의해 근사치로 계산되었다.그들이 더 잘 압축할수록 더 좋다.리, 오소리, 첸, 쿤, 키어니, 장(2001)은 이러한 접근방식의 최적화형식을 사용하였으며,^[57] 리, 리, 마, 비타니(2003)에 의한 최적의 정상화형식이 등장하여 클리비라시와 비타니(2005)에 의해 보다 광범위하게 증명되었다.^[59]오투와 사유드(2003)는 렘펠-지브 복잡성 방법을 사용하여 계통생성 나무 건축을 위한 다섯 가지 다른 거리 측도를 구축했다.^[60]null

컨텍스트 모델링 압축

컨텍스트 모델링 복잡도에서 하나 이상의 통계적 모델의 다음 심볼 예측은 결합되거나 과거에 기록된 사건에 기초한 예측을 산출하기 위해 경쟁한다.각 기호 예측에서 파생된 알고리즘 정보 콘텐츠는 시퀀스 길이에 비례하는 시간으로 알고리즘 정보 프로파일을 계산하는 데 사용할 수 있다.그 과정은 DNA 염기서열 분석에 적용되었다.^[61]null

그래픽 표현 기반 방법

반복 지도

시퀀스 분석을 위해 반복된 지도를 사용하는 것은 HJ 제프리가 1990년^[26] 카오스 게임을 적용하여 게놈 시퀀스를 단위 사각형으로 매핑하자고 제안하면서 처음 도입되었다.그 보고서는 그 절차를 CGR(Cause Game Presentation)이라고 만들었다.그러나 불과 3년 후 이 접근법은 N 골드먼에 의한 마르코프 전환표의 투영으로 처음 기각되었다.^[62]이러한 반대는 그 10년 말에 기각되었는데, 그 반대의 경우인 CGR이 간접적으로 마르코프 전환을 프랙탈, 무주문(무질서) 대표(도-무료)로 지도화한다는 것이다.^[63]반복된 지도가 상징적 공간과 숫자적 공간 사이에 편향적 지도를 제공한다는 것을 깨달음으로써 시퀀스 비교와 특성화에 대한 다양한 정렬이 없는 접근법을 식별하게 되었다.이러한 발전은 JS 알메이다 인에 의해 2013년 말에 검토되었다.^[64]https://usm.github.com과 같은 다수의 웹 앱을 통해 클라우드 컴퓨팅용으로 개발된 현대적인 맵리듀스 배포를 최대한 활용하는 방식으로 임의의 심볼 시퀀스를 인코딩하고 비교하는 방법을 시연할 수 있다.^[65]null

정렬 기반 방법과 정렬 없는 방법의 비교

선형 기반 방법	정렬이 필요 없는 방법
이 방법들은 동음이의 영역이 연속적이라고 가정한다(격차 포함)	호몰로게이션 영역의 경직성을 가정하지 않는다.
가능한 모든 쌍별 시퀀스 비교 계산. 따라서 계산 비용이 많이 든다.	하위 순서의 발생에 기초하여 구성; 계산적으로 저렴하고 기억력이 집중될 수 있다.
유전체학에서 확립된 접근법	비교적 최근 및 phylogenomics의 적용이 제한됨; 견고성과 확장성에 대한 추가 테스트 필요
대체/진화 모델 필요	대체/진화 모델에 대한 의존도가 낮음
확률적 시퀀스 변동, 재결합, 수평적(또는 측면) 유전적 전달, 이질성 비율 및 다양한 길이의 시퀀스에 민감하며, 특히 유사성이 "황혼화 영역"에 있는 경우	확률적 시퀀스 변동, 재조합, 수평(또는 측면) 유전적 전달, 이질성 비율 및 다양한 길이의 시퀀스에 덜 민감함
최소 O(n2)의 복잡성을 가진 추론 알고리즘을 사용하는 모범 사례, 시간 효율 낮음	추론 알고리즘은 일반적으로 O(n2) 이하, 더 시간 효율적인
자연에서 경험적 경험적 발견; 맞춤 점수가 동질학과 어떻게 관련되는지 통계적으로 유의한 점은 평가하기 어렵다.	정확한 해법; 시퀀스 거리(및 유사도)의 통계적 유의성을 쉽게 평가할 수 있다.
최적의 점수를 가진 정렬을 찾기 위해 동적 프로그래밍(컴퓨팅 비용이 많이 든다)에 의존한다.null	단어 수나 프랙탈 공간의 위치를 색인화하여 계산하는 사이드 스텝 계산 값비싼 동적 프로그래밍.[66]null

정렬되지 않은 방법의 적용

• 유전적 재배열^[67][68]
• 분자유전학^[9][14][69]
• 메타게노믹스^{[70][71][72][73][74]}
• 차세대 시퀀스 데이터 분석^[70][30]
• 후생유전체학^[75]
• 종의^[76] 바코드
• 인구유전학^[11]
• 수평유전자전달^[8]
• 바이러스^[21][77][78] 세로/유전자형화
• 알레르기성 예측^[79]
• SNP 검색^[80]
• 재조합검출^[81]

정렬되지 않은 방법을 위한 웹 서버/소프트웨어 목록

이름	설명	유용성	참조
프로트콤	가장 표현된 기능 점수 매기기 접근 방식	프로트콤프	[82]
kmacs	k-평균 공통 하위 문자열 접근법	kmacs	[36]
간격이 있는 단어	스페이스 워드 주파수	간결한 말.	[23]
코필로그	조립이 필요 없는 마이크로프로세서 접근법	코필로그	[44]
프로토스파엠	proteome 기반 간격 단어 일치	프로토스파엠	[48]
FSWM	필터링된 간격-단어 일치	FSWM	[46]
FFP	피쳐 주파수 프로파일 기반 계통 발생	FFP	[17]
CVTree	계통생성을 위한 컴포지션 벡터 기반 서버	CVTree	[83]
RTD 필로제니	계통생성을 위한 반환 시간 분배 기반 서버	RTD 필로제니	[21]
AGP	무정렬 게놈 유전자를 위한 멀티모드 웹 서버	AGP	[84]
알피	바이러스성 게놈과 박테리아성 게놈 간의 국소 유사성에 대한 정렬되지 않은 탐지	알피	[8]
디카페인+피	PYthon에서 Alignment-Free 방법을 사용한 DistancE 계산	디카페인+피	[85]
뎅게 서브티퍼	RTD 기반 뎅기 바이러스의 유전자형성	뎅게 서브티퍼	[21]
WNV 타이퍼	RTD에 기초한 웨스트 나일 바이러스의 유전자형성	WNV 타이퍼	[77]
알레르겐FP	설명자 지문에 의한 알레르기 예측	알레르겐FP	[79]
kSNP v2	정렬이 필요 없는 SNP 검색	kSNP v2	[80]
d2Tools	k-투플 주파수를 이용한 메타트랜스펙토믹 샘플 비교	d2Tools	[86]
허둥지둥하다	SHustring을 이용한 재결합 검출	허둥지둥하다	[81]
박살내다	유전적 재배열 감지 및 시각화	박살내다	[67]
스매시++	게놈 재배열 찾기 및 시각화	스매시++	[68]
GS콤프레어	박테리아 게놈의 올리고뉴클레오티드 기반 빠른 군집화	GS콤프레어	–
혜성	HIV-1, HIV-2 및 HCV 바이러스 시퀀스의 정렬되지 않은 하위 유형	혜성	[78]
USM	순서 정렬의 프랙탈 맵리듀스 분해	usm.github이오	[65]
매	고대 DNA의 메타게놈 구성을 유추하기 위한 무정렬 방법	매	[73]
크라켄	정확한 k-mer 일치를 이용한 분류법 분류	크라켄 2	[74]
CLC	참조 없는 k-mer 기반 일치를 사용한 계통발생 트리	CLC 미생물 게놈 모듈	[87]
이글	게놈 데이터에서 상대적인 부재 단어를 찾을 수 있는 초고속 도구	이글2	[88]

참고 항목

• 시퀀스 분석
• 다중 시퀀스 정렬
• 필로게노믹스
• 생물정보학
• 메타게노믹스
• 차세대 시퀀싱
• 인구유전학
• SNPs
• 재조합 탐지 프로그램
• 게놈 스키밍

참조