갭 페널티

Gap penalty

갭 페널티는 둘 이상의 시퀀스를 정렬하여 점수를 매기는 방법이다.시퀀스를 정렬할 때 시퀀스에 간격을 도입하면 정렬 알고리즘이 공백 없는 정렬보다 더 많은 항을 일치시킬 수 있다.그러나 유용한 맞춤을 만들기 위해서는 맞춤의 간격을 최소화하는 것이 중요하다.간격이 너무 많으면 정렬이 무의미해질 수 있다.간격 벌점은 간격의 수와 길이에 따라 정렬 점수를 조정하는 데 사용된다.갭 페널티의 5가지 주요 유형은 일정, 선형, 아핀, 볼록, 프로필 기반이다.[1]

적용들

  • 유전적 시퀀스 정렬 - 생물정보학에서 공백은 시퀀스의 삽입 또는 삭제에서 발생하는 유전적 돌연변이를 설명하기 위해 사용되며, 때로는 인델이라고도 한다.단일 돌연변이, 감수분열의 불균형 교차, 미끄러진 가닥 오파기, 염색체 변환 등으로 인해 삽입이나 삭제가 발생할 수 있다.[2]삽입 또는 삭제는 전체 하위 시퀀스를 구성하며 종종 단일 돌연변이 사건에서 발생하기 때문에 정렬의 간격 개념은 많은 생물학적 적용에서 중요하다.[3]게다가 단일 돌연변이 이벤트는 크기가 다른 차이를 만들 수 있다.따라서 점수를 매길 때 두 개의 DNA 시퀀스를 정렬할 때 점수 차이를 전체적으로 점수화할 필요가 있다.한 시퀀스의 다중 간격을 단일 공백이 클수록 돌연변이에 대한 높은 비용의 할당을 줄일 수 있다.예를 들어, 두 단백질 시퀀스는 상대적으로 비슷할 수 있지만 특정 간격으로 다를 수 있다. 한 단백질은 다른 단백질에 비해 다른 하위 단위를 가질 수 있기 때문이다.이러한 서로 다른 하위 단계를 공백으로 표현하면 시퀀스에 지워지지 않는 조작이 있는 긴 연속 실행이 있더라도 이러한 사례를 "좋은 일치"로 취급할 수 있을 것이다.따라서 좋은 갭 페널티 모델을 사용하면 선형에서 낮은 점수를 받지 않고 진정한 선형을 찾을 수 있는 기회를 개선할 수 있다.[3]유전적 시퀀스 정렬에서 간격은 단백질/DNA 시퀀스 정렬에서 대시(-)로 표현된다.[1]
  • Unix diff 함수 - 표절 탐지와 유사한 두 파일 간의 최소 차이 계산
  • 철자 검사 - 갭 벌칙은 철자가 틀린 단어에 대한 편집 거리가 가장 짧은 올바른 철자를 찾는 데 도움이 될 수 있다.공백은 철자가 틀린 단어에 글자가 누락된 것을 나타낼 수 있다.
  • 표절 탐지 - 갭 벌칙은 알고리즘이 원본 섹션에 간격을 두고 동일한 부분을 일치시킴으로써 문서의 섹션이 표절한 부분을 탐지할 수 있도록 한다.특정 문서에 대한 갭 벌칙은 주어진 문서의 어느 정도가 아마도 원본이거나 표절된 것인지 정량화한다.

생물정보학 응용 프로그램

전역 정렬

주요 기사:니들만-운슈 알고리즘

전역 정렬은 조회 시퀀스를 기준 시퀀스와 함께 엔드 투 엔드 정렬을 수행한다.이상적으로는 이 정렬 기법이 유사한 길이의 밀접하게 연관된 시퀀스에 가장 적합하다.니들맨-운슈 알고리즘은 글로벌 얼라인먼트를 수행하는 데 사용되는 동적 프로그래밍 기법이다.본질적으로 알고리즘은 문제를 하위문제 집합으로 나눈 다음, 하위문제 결과를 사용하여 원래의 질의에 대한 해결책을 재구성한다.[4]

반지구적 정렬

세미 글로벌 정렬의 사용은 큰 시퀀스 내에서 특정 일치를 찾기 위해 존재한다.예를 들어 DNA 서열 내에서 프로모터를 찾는 것이 포함된다.글로벌 정렬과 달리 한 시퀀스 또는 두 시퀀스의 끝없는 간격을 절충한다.만일 끝 갭이 시퀀스 2가 아닌 하나의 시퀀스 1로 벌칙을 받는다면, 시퀀스 1 내에 시퀀스 2가 포함된 정렬을 생성한다.

로컬 정렬

주요 기사:스미스-워터맨 알고리즘
text
단백질 시퀀스 정렬 예제

로컬 시퀀스 정렬은 한 시퀀스의 연속 하위 섹션과 다른 시퀀스의 연속 하위 섹션을 일치시킨다.[5]스미스-워터맨 알고리즘은 매치와 미스매치에 대한 점수를 부여함으로써 동기부여가 된다.일치는 정렬의 전체 점수를 증가시키는 반면 불일치는 점수를 감소시킨다.그러면 정렬이 잘되면 플러스 점수가 나오고 정렬이 잘 안 되면 마이너스 점수가 나온다.로컬 알고리즘은 긍정 점수를 매기는 선형만 고려하고 그 중에서 가장 좋은 선형을 선택하여 가장 높은 점수의 선형을 선택한다.알고리즘은 동적 프로그래밍 알고리즘이다.단백질을 비교할 때, 각각의 가능한 잔류물에 점수를 할당하는 유사성 행렬을 사용한다.점수는 유사한 잔류물에 대해 양수여야 하며 다른 잔류물 쌍에 대해서는 음수여야 한다.갭은 대개 갭 개구부에 대해 초기 벌칙을 할당하는 선형 갭 함수와 갭 확장에 대한 추가 벌칙을 사용하여 벌칙을 적용하여 갭 길이를 늘린다.

점수 매트릭스

주요 기사:대체 행렬
text
블로섬-62 매트릭스

BLOSUM과 같은 대체 행렬은 단백질의 시퀀스 정렬에 사용된다.[6]대체 행렬은 가능한 잔류물 쌍을 정렬하기 위한 점수를 할당한다.[6]일반적으로 서로 다른 치환 행렬은 서로 다른 각도로 분산되는 시퀀스 간의 유사성을 탐지하는 데 맞춤화된다.단일 행렬은 비교적 광범위한 진화적 변화에 비해 합리적으로 효율적일 수 있다.[6]BLOSUM-62 매트릭스는 약한 단백질 유사성을 탐지하는 가장 좋은 대체 매트릭스 중 하나이다.[6]높은 숫자의 BLOSUM 행렬은 밀접하게 관련된 시퀀스를 비교하도록 설계되었고, 낮은 숫자의 행렬은 먼 관련 시퀀스를 비교하도록 설계되었다.예를 들어 순서가 더 비슷한 선형에는 BLOSUM-80이, 서로 갈라진 선형에는 BLOSUM-45가 사용된다.[6]특히 길고 약한 선형의 경우 BLOSUM-45 행렬이 최상의 결과를 제공할 수 있다.짧은 선형은 BLOSUM-62보다 "상대 엔트로피"가 높은 매트릭스를 사용하여 더 쉽게 감지된다.BLOSUM 시리즈는 가장 짧은 쿼리에 적합한 상대 엔트로피를 가진 행렬을 포함하지 않는다.[6]

인델스

주요 기사:지우기

DNA 복제 중에 복제 기계는 DNA를 복제하는 동안 두 가지 유형의 오류를 발생시키기 쉽다.이 두 가지 복제 오류는 DNA 가닥(인델)에서 단일 DNA 베이스의 삽입과 삭제다.[7]인델은 DNA 가닥에 돌연변이를 일으켜 대상 단백질의 불활성화 또는 과활성화를 초래할 수 있는 심각한 생물학적 결과를 초래할 수 있다.예를 들어, 하나 또는 두 개의 뉴클레오티드 지워짐이 코딩 시퀀스에서 발생하는 경우 결과는 판독 프레임의 이동 또는 단백질을 비활성화할 수 있는 프레임-변형이 될 것이다.[7]인델의 생물학적 결과는 종종 해로우며 암과 같은 인간의 병리학과 자주 관련된다.그러나 모든 인델이 프레임에 의한 돌연변이는 아니다.만약 인델이 트리뉴클레오티드에서 발생한다면, 그 결과는 단백질 기능에 영향을 미칠 수 있는 단백질 서열의 확장이다.[7]

종류들

이 그래프는 갭 페널티 유형 간의 차이를 보여준다.정확한 숫자는 용도에 따라 변경되지만 이는 각 기능의 상대적 형태를 보여준다.

상수

이것은 가장 간단한 갭 페널티 유형이다: 길이와 상관없이 모든 갭에 고정된 마이너스 점수가 주어진다.[3][8]이것은 알고리즘이 더 큰 인접 부분을 남겨두고 더 적은, 더 큰 간격을 만들도록 장려한다. 

ATTGACCTGA AT--CCTGA

두 개의 짧은 DNA 시퀀스를 하나의 기본 쌍의 간격을 나타내는 '-'로 정렬.매 경기 1점 만점에 전체 점수 차가 -1이면 총점은 7 - 1 = 6이다.

선형

일정한 간격 벌칙에 비해 선형 간격 벌칙은 간격의 각 삽입/삭제 길이(L)를 고려한다.따라서 각 삽입/삭제 요소에 대한 벌점이 B와 간격 L의 길이인 경우 총 간격 벌점은 두 BL의 제품일 것이다.[9]이 방법은 점수 차이가 추가될 때마다 총점이 감소하면서 점수 차가 짧아지는 것을 선호한다. 

ATTGACCTGA AT--CCTGA

일정한 갭 페널티와 달리 갭의 크기를 고려한다.점수 1과 각 점수 차 -1로 경기를 치르면, 여기서 점수는 (7 - 3 = 4)이다.

아핀

가장 널리 사용되는 갭 페널티 기능은 아핀 갭 페널티다.어핀 갭 벌칙은 갭 벌칙과 선형 갭 벌칙의 구성요소를 결합하여 A + 의 형태를 취하며 이로써 A는 갭 개방 벌칙, B는 갭 연장 벌칙, L은 갭 길이라는 새로운 용어를 도입하였다.갭 오프닝이란 어떤 길이의 간격을 벌리기 위해 필요한 비용을 말하며, 갭을 기존 갭의 길이를 1로 연장하는 비용을 말한다.[10]목적에 따라 다르기 때문에 A와 B가 어떤 값이어야 하는지가 명확하지 않은 경우가 많다.일반적으로 관심사가 밀접하게 관련된 일치 항목(예: 게놈 염기서열 분석 중 벡터 염기서열 제거)을 찾는 것이라면 갭을 줄이기 위해 갭 페널티를 높여야 한다.반면 좀 더 먼 경기 찾기에 관심이 있을 때는 갭 페널티를 낮춰야 한다.[9]A와 B의 관계도 갭 크기에 영향을 미친다.간극의 크기가 중요한 경우, 작은 A와 큰 B(간격을 연장하는 데 더 많은 비용이 소요됨)를 사용하며, 그 반대의 경우도 마찬가지다.동일한 양의 상수 k를 곱하면 모든 벌칙이 k:kA+kBL = k(A+BL) 증가하므로 A/B 비율만 중요하다.

볼록스

부착된 간격 벌칙을 사용하려면 간격의 개방과 확장에 대해 고정 벌칙 값을 할당해야 한다.이것은 생물학적 맥락에서 사용하기에는 너무 딱딱할 수 있다.[11]

로그 간격은 ( )= + C L 형식을 취하며, 지워지지 않는 크기의 분포가 전원법을 준수한다는 연구 결과가 제시되어 제안되었다.[12]아핀 갭의 사용과 관련하여 제안된 또 다른 이슈는 시퀀스를 더 짧은 갭과 정렬하는 편애다.로그 간격 벌칙은 긴 간격이 바람직하도록 부착된 간극을 수정하기 위해 고안되었다.[11]그러나 이와는 대조적으로 로그 모델을 사용했을 때 아핀 모델에 비해 정렬 상태가 좋지 않았던 것으로 밝혀졌다.[12]

프로파일 기반

프로파일-프로파일 정렬 알고리즘은 정렬 정확도가 개선된 단백질 호몰로지 관계를 탐지하는 강력한 도구다.[13]프로파일 정렬은 PSI-BLAST 검색에 의해 생성된 다중 시퀀스 정렬에서 통계적으로 지워지지 않는 주파수 프로파일을 기반으로 한다.[13]아미노산 쌍의 유사성을 측정하기 위해 대체 행렬을 사용하는 대신, 종단-종단 정렬 방법에는 종단 벡터 쌍의 유사성을 측정하는 종단 기반 채점 기능이 필요하다.[13]프로파일 정렬은 갭 페널티 기능을 사용한다.간격 정보는 보통 지워지지 않는 주파수 프로파일의 형태로 사용되는데, 이는 시퀀스가 정렬되는 데 더 구체적이다.ClustalW와 MAFFT는 다중 시퀀스 정렬에 대해 이러한 종류의 갭 페널티 결정을 채택했다.[13]정렬 정확도는 특히 염기서열 정체성이 낮은 단백질의 경우 이 모델을 사용하여 개선할 수 있다.일부 종단-종단 정렬 알고리즘은 채점 기능에 2차 구조 정보를 하나의 용어로 실행하므로 정렬 정확도가 향상된다.[13]

시간 복잡성 비교

추가 정보:시간 복잡성

계산 생물학에서 정렬의 사용은 종종 다양한 길이의 순서를 포함한다.알려진 입력 크기로 효율적으로 실행되는 모델을 선택하는 것이 중요하다.알고리즘을 실행하는 데 걸리는 시간을 시간 복잡성이라고 한다.

다양한 갭 패널티 모델의 시간 복잡성
유형 시간
일정 간격 벌칙 O(mn)
어핀 갭 페널티 O(mn)
볼록 갭 페널티 O(mn lg(m+n))

과제들

격차와의 협력에 있어서는 몇 가지 난제가 있다.인기 있는 알고리즘으로 작업할 때 갭 페널티 기능의 형태에 대한 이론적 근거는 거의 없어 보인다.[14]따라서 어떤 정렬 상황의 경우 간격 배치를 경험적으로 결정해야 한다.[14]또한, 아핀 갭 벌칙과 같은 쌍방향 정렬 갭 벌칙은 삽입 또는 삭제된 조각의 아미노산 유형이나 깨진 끝단에 독립적으로 시행되는 경우가 많은데, 이는 갭 영역에서 특정 잔여 유형을 선호한다는 증거에도 불구하고 말이다.[14]마지막으로, 시퀀스의 정렬은 해당 구조의 정렬을 의미하지만, 단백질의 틈새의 구조적 특징과 그에 상응하는 시퀀스 사이의 관계는 불완전하게 알려져 있을 뿐이다.이것 때문에 구조 정보를 갭 페널티에 포함시키는 것은 어렵다.[14]일부 알고리즘은 예측 또는 실제 구조 정보를 사용하여 간격의 배치를 편향시킨다.그러나, 오직 소수 시퀀스만이 알려진 구조를 가지고 있으며, 대부분의 정렬 문제는 알려지지 않은 2차 및 3차 구조의 시퀀스를 포함한다.[14]

참조

  1. ^ a b "Glossary". Rosalind. Rosalind Team. Retrieved 2021-05-20.
  2. ^ Carroll, Ridge, Clement, Snell, Hyrum , Perry, Mark, Quinn (January 1, 2007). "Effects of Gap Open and Gap Extension Penalties" (PDF). International Journal of Bioinformatics Research and Applications. Retrieved 2014-09-09.{{cite journal}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  3. ^ a b c "Gap Penalty" (PDF). Algorithms for Molecular Biology. 2006-01-01. Archived from the original (PDF) on 2013-06-26. Retrieved 2014-09-13.
  4. ^ Lesk, Arthur M (2013-07-26). "bioinformatics". Encyclopædia Britannica. Encyclopædia Britannica. Retrieved 2014-09-12.
  5. ^ Vingron, M.; Waterman, M. S. (1994). "Sequence alignment and penalty choice. Review of concepts, case studies and implications". Journal of Molecular Biology. 235 (1): 1–12. doi:10.1016/S0022-2836(05)80006-3. PMID 8289235.
  6. ^ a b c d e f "BLAST substitution matrices". NCBI. Retrieved 2012-11-27.
  7. ^ a b c Garcia-Diaz, Miguel (2006). "Mechanism of a genetic glissando: structural biology of indel mutations". Trends in Biochemical Sciences. 31 (4): 206–214. doi:10.1016/j.tibs.2006.02.004. PMID 16545956.
  8. ^ "Glossary - Constant Gap Penalty". Rosalind. Rosalind Team. 12 Aug 2014. Retrieved 12 Aug 2014.
  9. ^ a b Hodgman C, French A, Westhead D (2009). BIOS Instant Notes in Bioinformatics. Garland Science. pp. 143–144. ISBN 978-0203967249.
  10. ^ "Global Alignment with Scoring Matrix and Affine Gap Penalty". Rosalind. Rosalind Team. 2012-07-02. Retrieved 2014-09-12.
  11. ^ a b Sung, Wing-Kin (2011). Algorithms in Bioinformatics : A Practical Introduction. CRC Press. pp. 42–47. ISBN 978-1420070347.
  12. ^ a b Cartwright, Reed (2006-12-05). "Logarithmic gap costs decrease alignment accuracy". BMC Bioinformatics. 7: 527. doi:10.1186/1471-2105-7-527. PMC 1770940. PMID 17147805.
  13. ^ a b c d e Wang C, Yan RX, Wang XF, Si JN, Zhang Z (12 October 2011). "Comparison of linear gap penalties and profile-based variable gap penalties in profile-profile alignments". Comput Biol Chem. 35 (5): 308–318. doi:10.1016/j.compbiolchem.2011.07.006. PMID 22000802.
  14. ^ a b c d e Wrabl JO, Grishin NV (1 January 2004). "Gaps in structurally similar proteins: towards improvement of multiple sequence alignment". Proteins. 54 (1): 71–87. doi:10.1002/prot.10508. PMID 14705025. S2CID 20474119.

추가 읽기