NGS - STAR 정렬

Junho_Mun·2025년 11월 5일

STAR 란 ?

STAR는 Spliced Transcripts Alignment to a Reference의 약자로
스플라이싱이 일어난 RNA 리드를 유전체에 정렬하는 빠른 프로그램이다.

STAR는 인덱싱을 하여 접미사 배열(Suffix Array)을 만든후, 시드 탐색을 통해 최대 매핑 가능 접두사(Maximal Mappable Prefix, MMP) 를 찾는다.
이후 시드 클러스터링 및 스플라이싱을 한 후 해당 정렬본을 평가하고 출력하는 매커니즘을 가지고 있다.

1. 인덱싱

STAR는 정렬을 시작하기 전에, 참조 유전체(Reference Genome, .fasta)를 가지고 접미사 배열(Suffix Array) 이라는 자료구조를 사용하여 인덱스 파일을 만든다.

접미사 배열이란?

유전체 서열에서 가능한 모든 부분 문자열(Suffix)을 가져와서 사전순으로 정렬한 리스트이다.
예를 들어, BANANA라는 문자열이 있다면 A,ANA,BANANA,NA,NANA라는 조각들이 나올텐데, ANA라는 조각을 찾고 싶다면 이 배열에서 A로 시작하는 부분을 보면 되므로 전체에서 ANA를 탐색하는것 보다 빠르다. 시간 복잡도 = $O(M \log N)$

다음과 같은 접미사 배열을 유전체에 적용하여 참조가능한 색인(index) 를 만들고, 이 정렬된 목록에 '위치 값'을 기록해 둔다.

ex : GATTACA
sorted : A / ACA / ATTACA / CA / GATTACA / TACA / TTACA
position A: 6 / 4 / 1 / 5 / 0 / 3 / 2

STAR는 전체 접미사 배열을 메모리에 올리면 너무 과도한 용량을 요구하기에, genomeParameters.txt에 정의된 특정 길이를 기반으로 압축되고 희소한 Suffix Array를 생성하여 메모리 사용량을 조절한다. ( --genomeSAindexNbits)

2. 시드 탐색

1. MMP ( Maximal Mappable Prefix ) 탐색

STAR는 주어진 리드에서 최대 매핑 가능 접두사(Maximal Mappable Prefix, MMP) 를 찾는것을 최우선으로 한다.
MMP 는 리드의 맨 앞에서부터 시작해서, 인덱싱된 참조 유전체와 100% 일치하는 가장 긴 조각 을 의미한다.

예를 들어, 1번~28번 염기(28bp)가 100% 일치하고, 29번 염기에서 mismatch가 발생했다면, MMP1은 1번 염색체 1000 ~ 1027 위치에 매핑된다.

2. 연속 탐색

mismatch가 발생한 29번 염기로부터 리드의 끝을 새로운 리드로 간주하고, 두번째 MMP를 탐색한다.

결론적으로, 한 리드가 여러개의 시드(seed) 조각으로 분해되고, 각 시드가 유전체 어디에 매핑되는지에 대한 위치 목록이 나온다.

Seed 1 (28bp) : chr1:1000-1027
Seed 2 (27bp) : chr1:1028-1054
Seed 3 (40bp) : chr1:50000-50039

다음을 보면, Seed1과 Seed2의 위치는 가까운 반면 Seed3과는 굉장히 멀리 있음을 알 수 있다. 이런 분해된 시드들을 어떻게 연결하고 판단하는지에 대한 과정이 다음 단계인 시드 체이닝 및 스코어링 이다.

3. 시드 체이닝(Chaining) 및 스코어링(Scoring)

동적 프로그래밍을 사용하여 분해된 seed 사이의 최고 점수 경로를 찾는다.

Seed 1 + Seed 2 연결 :
- Seed 1의 끝과 Seed 2의 시작이 정확히 이어진다.
- Gap = 0
- 패널티 없음
Seed 2 + Seed 3 연결 :
- Seed 2의 끝과 Seed 3의 시작 사이에는 거대한 Gap이 있다.
- STAR는 이 Gap이 이미 알려진 것인지 스플라이스 정션 데이터베이스에서 조회를 한다.
- Case 1 : 이미 알려진 경우
  SJDB에 이미 있는 경우, 해당 구간은 Intron구간이므로 패널티 없음.
  - Case 2 : DB에 없지만, 표준 스플라이싱 신호와 일치
  DB에 없지만, 틈의 경계가 GT-AG등 표준 스플라이싱 신호(Canoical motif)와 일치하다면 낮은 패널티.(--alignIntroMin에 기반)
  - Case 3 : DB에도 없고, 경계도 이상함..
  매우 높은 패널티.
  - Case 4 : 틈이 매우 작을때 (스플라이싱이 아님)
  Indel 패널티(삽입,삭제 패널티)가 적용된다.