📂알고리즘

서열정렬에서의 치환행렬

정의

서열정렬 점수를 매길 때 매치와 미스매치의 기준이 되는 행렬을 치환행렬^{substitution matrix}이라 한다.

예시

using BioAlignments

EDNAFULL
BLOSUM45
PAM30

거두절미하고 예시부터 보자. 줄리아에서는 BioAlignments라는 패키지가 나와있고 손쉽게 원하는 치환행렬을 불러들일 수 있다. DNA 분석에 자주 사용되는 EDNAFULL나 단백질 서열에 쓰이는 BLOSUM(BLOcks SUbstitution Matrix), PAM(Point Accepted Mutation) 행렬을 불러보면 다음과 같다.

매치라고 다 같은 매치가 아니고, 미스매치라고 다 같은 매치가 아닌 것은 어떤 빈도적인 인사이트를 반영하기 위함이다. 정보검색이론 등에서 생각할 수 있는 예로는 키보드 자판 위치에 따른 오탈자 보정이 있다. 가령 “juloa"라는 의미 없는 단어를 생각해봤을 때, 쿼티 자판 상 i와 o는 바로 옆자리기 때문에 julia의 오타라고 추측할 수 있게끔 i와 o 사이에 낮은 미스매치 페널티를 주는 게 합리적일 수 있다. julea 역시 julia의 오타일 수는 있지만, i와 e 사이의 거리가 멀기 때문에 같은 오탈자라도 juloa에 비해 우연히 틀렸을거라고는 덜 의심하는 것이다.