데드 엔드 제거

데드 엔드 제거 알고리즘(DEE)은 이산형 독립 변수 집합에 걸쳐 함수를 최소화하는 방법이다.기본 아이디어는 "사망" 즉, 항상 더 나은 조합 또는 동등한 조합으로 그러한 조합을 대체하는 방법이 있기 때문에 글로벌 최소값을 정의할 필요가 없는 변수의 조합을 식별하는 것이다.그렇다면 우리는 그러한 결합을 더 이상 검색하는 것을 삼갈 수 있다.따라서 데드엔드 제거는 동적 프로그래밍의 미러 이미지로, "좋은" 조합을 식별하고 더 자세히 탐구한다.방법 자체는 일반적이지만 주로 단백질의 구조를 예측하고 설계하는 문제점에 대해 개발하여 적용하고 있다.그것은 제약조건 만족 문제에서 대체 가능성으로도 알려진 최적화의 지배 개념과 밀접하게 관련되어 있다.데드 엔드 제거 정리에 대한 원래의 설명과 증거는 에서 찾을 수 있다.

기본요구사항

효과적인 DE 구현에는 다음과 같은 네 가지 정보가 필요하다.

1. 잘 정의된 이산 독립 변수 유한 집합
2. 변수 집합의 각 원소와 관련된 사전 계산된 숫자 값("에너지"로 간주됨) (아마도 이들의 쌍, 삼배 등)
3. 요소가 "막다른 끝"인 경우, 즉 솔루션 세트의 구성원이 될 수 없는 경우를 결정하는 기준 또는 기준 또는 기준
4. 최소화할 목표 기능("에너지 기능" 고려)

주어진 함수의 최대값도 식별하기 위해 기준을 쉽게 변경할 수 있다는 점에 유의하십시오.

단백질 구조 예측에 응용

데드 엔드 제거는 에너지 함수 $E{\displaystyle }$ ${\displaystyle E}$를 최소화하여 주어진 단백질 백본 구조에서 사이드 체인의 구조를 예측하는 데 효과적으로 사용되어 왔다$.$사이드 체인의 이음각 검색 공간은 단백질 내 각 아미노산 위치(분명 고정된 길이)에 대해 별도의 로타머 집합으로 제한된다.원래 DE 설명은 확장될 수 있지만 단일 로타머와 로타머 쌍의 제거 기준을 포함했다.

다음 논의에서는 $N{\displaystyle }$ ${\displaystyle N}$을(를) 단백질의 길이로 하고$$ $r{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$을(를) $k{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {t\mathrm{}}^{}}$ ${\displaystyle {\mathrm{h}}^{}}$ ${\$ 사이드$$$$체인의 로타머를 나타내도록$$ 한다.단백질에 있는 원자는 오직 두 개의 신체 전위에 의해서만 상호작용을 하는 것으로 가정되기 때문에, 그 에너지는 쓰여질 수도 있다.

${\displaystyle E_{TOT}=\sum _{k}{k_{k}(r_{k})+\sum _{k\neq l}E_{kl}(r_{k},r_{l})\,}$

Where ${\displaystyle E_{k}(r_{k})}$ represents the "self-energy" of a particular rotamer ${\displaystyle r_{k}}$, and ${\displaystyle E_{kl}(r_{k},r_{l})}$ represents the "pair energy" of the rotamers ${\displaystyle r_{k},r_{j}}$.

또한 ${\displaystyle {\mathrm{Ek}}_{}{}_{}^{}}$ k ${\displaystyle {}_{}^{}}$, r ${\displaystyle {}_{}^{}}$ A${\displaystyle {}_{}^{}}$) ${\displaystyle E_{k}(r_{k}^{a}^{A},$ 즉 로타머와 그 자체 사이의 쌍 에너지)는 0으로 간주되므로 합계에 영향을 주지 않는다.이 표기법은 아래 쌍 기준의 설명을 단순화한다.

단일 제거 기준

사이드체인 $k{\displaystyle }$ ${\displaystyle k}$의 특정 로타머 ${\displaystyle r_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$가 동일한 사이드체인의 다른$$ 로타머 ${\displaystyle r_{}^{}}$ B ${\$보다 더 나은 에너지를 줄 수 없는$$ 경우 로타머 A를 추가 검토에서 제거할 수 있어 검색 공간이 줄어든다.수학적으로 이 조건은 불평등에 의해 표현된다.

${\displaystyle E_{k}(r_{k}^{A})+\sum _{l=1}^{N}\min _{X}E_{kl}(r_{k}^{A}^},r_{l}^{X}).E_{k}(r_{k}^{B})+\sum _{l=1}^{N}\max _{X}E_{kl}(r_{k}^{B}},r_{l}^{X}}}}}}}}}$

where ${\displaystyle \min _{X}E_{kl}(r_{k}^{A},r_{l}^{X})}$ is the minimum (best) energy possible between rotamer ${\displaystyle r_{k}^{A}}$ of sidechain ${\displaystyle k}$ and any rotamer X of side chain ${\displaystyle l}$. Similarly, ${\displaystyle \underset{X}{max}{E}_k}$${\displaystyle \max _{X}E_{kl}(r_{k}^{B},r_{l}^{X})}$ is the maximum (worst) energy possible between rotamer ${\displaystyle r_{k}^{B}}$ of sidechain ${\displaystyle k}$ and any rotamer X of side chain ${\displaystyle l}$.

페어 제거 기준

쌍의 기준은 기술하고 구현하기 더 어렵지만 상당한 제거력을 추가한다.간결성을 위해 속기 변수 $U{\displaystyle {}_{}^{}}$ ${\displaystyle k_{}^{}}$ l ${\displaystyle A_{}^{}}$ ${\displaystyle B_{}^{}}$ ${\$$AB}}$은(는) 각 $위치{\displaystyle }$ k$${\$displaystyle k}$ $및{\displaystyle }$ l$${\$displaystyle l$}에서 로타머 A ${\displaystyle A}$ 및$$ $B{\displaystyle }$ ${\displaystyle B}$ 쌍의 고유 에너지입니다$.$

${\디스플레이 스타일 U_{kl}^{AB}\ {\stackrel {\mathrm {def}{}}{=}\ E_{k}(r_{k}^{A})++E_{l}(r_{l}^{B})+E_{kl}(r_{k}^{A},r_{l}^{B}})}$

각각$$$k{\displaystyle }$ ${\displaystyle k}$ 및 $l{\displaystyle }$ ${\displaystyle l}$ 위치에$$$$ 있는 지정된 $로타머{\displaystyle }$ A$${\$displaystyle A$} $및$ B ${\displaystyle$B} 쌍은$$ 항상 $C{\displaystyle }$ ${\displaystyle C$$}$ $및{\displaystyle }$ D ${\displaystystyle D}$ 쌍이 있는 경우 (하나) 모두 최종 솔루션에 포함될 수 없다.더 나은 에너지수학적으로 표현하면

${\디스플레이 스타일 U_{kl}^{AB}+\sum _{i=1}^{N}\min _{X}\좌측(E_{ki})(r_{k}^{A},r_{i}^{X})++E_{lj}(r_{l}^{B},r_{j}^{X}\right) >U_{kl}^{CD}+\sum _{i=1}^{N}\max _{X}\{X}\left(E_{ki})(r_{k}^{C},r_{i}^{X})+E_{lj}(r_{l}^{D},r_{j}^{X}\right)}}$

여기서 $A{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle C}$ ${\displaystyle A\neq C$ $B{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle D}$ ${\displaystyle B\neq$ $D$$}$ 및$$ $k{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle l}$ ${\displaystyle k\neq$ l$\}.$

에너지 행렬

큰 $N{\displaystyle }$ ${\displaystyle N}$의 경우$,$ 사전 계산된 에너지의 행렬은 저장 비용이 많이 들 수 있다.위와 같이 $N{\displaystyle }$ ${\displaystyle N}$을(를) 아미노산 위치의 개수로 하고$$, $p{\displaystyle }${\$displaystyle p}$을(를) 각 위치의 로타머의 개수로 한다$$(이는 일반적으로 모든 위치에서 일정하지만 반드시 일정한 것은 아님).주어진 위치에 대한 각 자체 에너지 매트릭스는 $p{\displaystyle }$ ${\displaystyle p$$}$ 항목을$$ 필요로 하므로 저장할 총 자기 에너지의 수는 ${\displaystyle N}$ ${\displaystyle p_{}}$ ${\displaystyle Np}$이다$.$ $p{\displaystyle }$ ${\displaystyle$ $r_{k}$와 $l{\displaystyle {}_{}}$ ${\$ $r_$${l$ 사이의$$ 각 쌍 에너지 매트릭스.각 위치에서, $p{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle p}$ ${\displaystyle p\buffs p}$ 행렬이$$ 필요하다.이렇게 하면 축소되지 않은 페어 매트릭스 $N{\displaystyle {}^{}}$ ${\displaystyle {2p\mathrm{}}^{}}$ 2${\$ N$^{2}p^{2}}.$페어 에너지는 대칭이고 로타머와 그 자체 사이의 페어 에너지는 0이기 때문에 구현 시 추가적인 복잡성의 비용으로 다소 줄일 수 있다.

구현 및 효율성

위의 두 가지 기준은 일반적으로 정합화 때까지 반복적으로 적용되며, 더 이상 로타머나 쌍을 제거할 수 없는 지점으로 정의된다.이것은 일반적으로 표본 공간의 크기가 많은 순서에 의해 감소하기 때문에 단순 열거하면 이 축소 집합 내의 최소값을 결정하는 데 충분할 것이다.

이 모델을 고려할 때, DE 알고리즘이 최적의 솔루션을 찾을 수 있다는 것이 확실하다. 즉, 그것은 글로벌 최적화 과정이다.단일 로타머 검색은 총 로타머 수에 맞춰 2차적으로 확장된다.페어 검색은 입체적으로 스케일링되며 알고리즘에서 가장 느린 부분이다(에너지 계산에서 제외).$이$는 O${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle N^{}}$) ${\displaystyle O(p^{N})$로 확장되는 흉물 강제 열거에 비해 획기적으로 개선된 것이다$.$

단백질 구조 예측 및 설계의 대안적 방법과 비교한 대규모의 DE 벤치마크는 DE가 합리적인 시간^[2] 내에 실행되는 단백질 길이의 최적 솔루션으로 신뢰성 있게 수렴한다는 것을 발견한다.평균장 이론, 유전 알고리즘, 몬테카를로 방법에서 파생된 기법을 포함하는 고려 중인 대안들을 크게 능가한다.그러나 다른 알고리즘은 DE보다 상당히 빠르기 때문에 더 크고 복잡한 문제에 적용할 수 있다. DE가 접근할 수 있는 문제 범위 내에서 DE 솔루션과의 비교에서 상대적 정확도를 추정할 수 있다.

단백질설계

앞의 논의에서는 로타머 $r{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$가 모두 동일한 아미노산 사이드 체인의 서로 다른 방향이라고$$ 암묵적으로 가정했다.즉, 단백질의 순서는 고정된 것으로 가정되었다.$또한{\displaystyle }$ 해당 위치에 대한 로타머 집합에 두 가지 유형의 사이드 체인을 모두 포함시킴으로써$$ 위치 k ${\displaystyle k}$에 대해 복수의 사이드 체인이 "경쟁"할 수 있다.이것은 주어진 단백질 등뼈에 새로운 순서를 설계할 수 있게 해준다.짧은 아연 손가락 단백질 접히는 이런 방식으로 재설계되었다^[3].그러나, 이것은 위치당 로타머의 수를 크게 증가시키고 여전히 고정된 단백질 길이를 요구한다.

일반화

예측과 설계 애플리케이션 모두에 대해 방법의 효율성과 제거 능력을 모두 향상시키는 보다 강력하고 일반적인 기준이 도입되었다.예를 들어, Goldstein 기준이라고^[4] 알려진 단일 제거 기준을 개선한 것이 있다. 이는 최소화를 적용하기 전에 상당히 간단한 대수적 조작에서 비롯된다.

${\displaystyle E_{k}(r_{k}^{A})-E_{k}(r_{k}^{B})+\sum _{l=1}^{N}\min _{X}\left(E_{kl}(r_{k}^{A},r_{l}^{X})-E_{kl}(r_{k}^{B},r_{l}^{X})\right)>0}$

$따라서{\displaystyle {}_{}}$ ${\displaystyle {Rotamer}_{}}$ $r{\displaystyle {}_{}^{}}$ K {\$displaystyle$ r_{k$}^{A$$}}$에 있는 세트에서 나온 어떤 대체 로타머가 ${\displaystyle r_{}^{}}$ ${\displaystyle {}_{}^{}}$$$${\$보다 총 에너지에 덜 기여하는$$ 경우 제거될 수 있다$$$.$ 이는 가능한 최선의 비교가 필요한 원래의 기준보다 개선된 것이다(tha).t는, 대체 로타머의 기여도가 가장 낮은$$, $r{\displaystyle {}_{}^{}}$ k ${\displaystyle {}_{}^{}}$ ${\$의 에너지 기여도가 가장 작다.

정교한 DE 기준과 이들의 상대적 성과 벤치마크에 대한 확대된 논의는 에서 찾을 수 있다.

참조

1. ^ 데스메트 J, 드 마이어 M, 헤이즈 B, 래스터 I. (1992)데드 엔드 제거 정리 및 단백질 사이드 체인 위치 지정에 사용.자연, 356, 539-542. PMID 21488406.
2. ^ Voigt CA, Gordon DB, Mayo SL. (2000)속도에 대한 거래 정확도: 단백질 시퀀스 설계에서 검색 알고리즘의 정량적 비교.J Mol Biol 299(3):789-803.
3. ^ 다히야트 BI, Mayo SL. (1997)De novo 단백질 설계: 완전 자동 시퀀스 선택.과학 278 (5335):82-7.
4. ^ Goldstein RF. (1994년).단백질 측면 체인과 관련 스핀 안경에 적용된 효율적인 로타머 제거.바이오피스 J 66(5):1335-40.
5. ^ 피어스 NA, 스피릿 JA, 데스메트 J, 마요 SL(2000)순응적 분할: 데드엔드 제거를 위한 보다 강력한 기준.J Compute Chem 21: 999-1009.