Inchworm 알고리즘

Inchworm이란?

Trinity 속에서 이용되고 있는, read를 대략적으로 조립해 contig를 생성하는 알고리즘입니다. 여기에서는 그 개요를 기술하고 있습니다.

리드, 커버리지에 대한 설명은 이쪽의 자료을 참조하십시오.

알고리즘

여기에서는 7 염기에 주목해 갑니다(k-mer의 k=7로 합니다). 위 그림의 왼쪽과 같이 GATTACA라는 7 염기 서열의 커버리지가 10이라고 가정합니다. 가장 오른쪽 A에서 1 염기 분만큼 가지를 늘려갑니다. 그러자 ATTACAG의 커버리지는 4, ATTACAA는 0, ATTACAT은 1, ATTACAC는 4인 것을 알았습니다. 다음은 가장 커버리지가 높은 ATTACAG와 ATTACAC에 주목합니다.

ATTACAG측
여기에서 1 염기를 늘립니다. 그러자 TTACAGA가 가장 커버리지가 높은 5인 것을 알았습니다.

ATTACAC측
이쪽도 1 염기만 늘립니다. 그러자 이쪽은 TTACACG, TTACACA, TTACACT, TTACACC의 커버리지는 1인 것을 알았습니다.

양측의 결과를 비교하면 TTACAGA가 가장 커버리지가 높다는 것을 알았다.
여기에서 GATTACAGA라는 염기서열이 원래 데이터에도 있는 것은 아닌가를 알 수 있습니다.
마찬가지로 왼쪽에도 염기의 가지를 펼쳐 가고, 이 contig를 작성해 갑니다.