페어와이즈 알고리즘

Pairwise Algorithm

Pairwise Algorithm은 동적 프로그래밍에서 유래한 알고리즘 기법입니다.페어와이즈 알고리즘은 단백질 프로파일(하나 이상의 배열된 배열에 대한 잔기 스코어링 매트릭스)을 DNA 가닥의 3개의 변환 프레임과 비교하는 것을 포함한 몇 가지 용도를 가지며 프레임시프트를 가능하게 한다.다른 단백질-DNA 정렬 도구와 비교하여 PairWise의 가장 주목할 만한 기능은 정렬 중에 프레임 이동을 허용한다는 것입니다.

역사

PairWise를 생물 정보학 문제에 가장 먼저 적용한 것 중 하나는 이완 버니(Ewan Birney)였습니다.

프레임시프트란 하나의 DNA 가닥에 여러 개의 변환 프레임이 존재하는 현상을 말합니다.일반적인 단백질-DNA 정렬 도구의 경우, 그들은 먼저 DNA를 단백질 배열로 변환하는 세 가지 프레임 중 하나를 선택한 후 주어진 단백질과 비교합니다.이러한 정렬은 전체 DNA 가닥에 대해 DNA 변환 프레임이 중단되지 않는다는 가정에 기초합니다.그러나 이것은 일반적으로 사실이 아니다.

PairWise 알고리즘은 Smith-Waterman 알고리즘의 best local alignment 알고리즘의 변형입니다.이러한 알고리즘은 모두 최소 문자열 편집 알고리즘으로 알려진 클래스에 속합니다.PairWise와 다른 얼라인먼트알고리즘의 주요 차이점은 GOP(Gap Opening Penalty), GEP(Gap Extension Penalty) 및 Match(Match)와 같은 일반 패널티 외에 프레임 확장 패널티(FOP)와 프레임 확장 패널티(FEP)라는 새로운 패널티를 도입했다는 점입니다.이 패널티는 프레임 확장 및 시 발생합니다.각각 다음과 같다.

일러스트

그림 1은 정상적인 단백질-DNA 정렬 알고리즘을 사용하여 하나의 단백질 배열과 하나의 DNA 배열을 정렬했을 때의 정렬 결과를 보여준다.사용된 프레임은 DNA 염기서열용 프레임1이었습니다그림과 같이 배열에 2개의 아미노산(6개의 핵산)의 갭이 있어 총점 -2의 낮은 점수를 얻었다.그림 1

그림 2는 PairWise를 사용하여 정렬된 결과를 보여 줍니다.동일한 DNA와 단백질 배열을 사용하고 아래와 같이 패널티를 수정한다.화살표는 프레임 시프트가 발생한 위치를 가리키고 있습니다.그 뉴클레오티드(G)에서는 번역 프레임이 프레임 1에서 프레임 2(점선)로 이동했다.이 변경으로 인해 9점 만점으로 정렬이 훨씬 개선되었습니다.

Figure 2

레퍼런스

  1. ^ Birney, E.; Thompson, J.; Gibson, T. (1996). "PairWise and SearchWise: Finding the optimal alignment in a simultaneous comparison of a protein profile against all DNA translation frames". Nucleic Acids Research. 24 (14): 2730–2739. doi:10.1093/nar/24.14.2730. PMC 145991. PMID 8759004.