Euclidean distance geometry and applications

Leo Liberti; Carlile Lavor; Nelson Maculan; Antonio Mucherino

Source-linked AI summary

Euclidean distance geometry and applications

Leo Liberti, Carlile Lavor, Nelson Maculan, Antonio Mucherino

arXiv:1205.0349v12012년 5월 2일q-bio.QM

TL;DR

Euclidean distance geometry는 불완전한 거리 데이터로부터 점을 어떻게 실현할지 묻는 분야로, molecular conformation, sensor-network localization, statics의 기반이 되는 문제를 다룬다. 이 survey는 이론과 응용을 종합하고, 알고리즘과 tractable subclass를 조명하면서, 성숙한 분야가 유익한 결과를 제공하지만 완전히 다루기에는 한계가 있다고 결론짓는다.

문제
Distance Geometry Problem은 가중 그래프의 거리를 지정된 Euclidean space의 점들로 실현할 수 있는지 묻는다.
방법
이 논문은 molecular conformation, sensor localization, statics에서의 Euclidean distance geometry 이론, 알고리즘, 응용을 survey한다.
결과
이 survey는 주요 이론적 결과와 응용을 유익하게 설명하며, 수천 개의 vertex와 edge를 가진 graph를 5초 이내에 실현하는 방법도 포함한다.
시사점 및 한계
Euclidean distance geometry는 부분적인 거리 정보를 활용하는 biological, statistical, engineering 응용을 위한 성숙한 기반을 제공한다.
시사점 및 한계
Hydrogen-only discretization은 인공 instance에서는 작동하지만 실제 NMR 데이터에서는 한계가 있어 재정렬이 필요하다.

Abstract

from arXiv · show

Euclidean distance geometry is the study of Euclidean geometry based on the concept of distance. This is useful in several applications where the input data consists of an incomplete set of distances, and the output is a set of points in Euclidean space that realizes the given distances. We survey some of the theory of Euclidean distance geometry and some of the most important applications: molecular conformation, localization of sensor networks and statics.

1 서론

Distance Geometry는 거리 개념을 통해 Euclidean geometry를 연구하며, weighted graph 데이터가 지정된 Euclidean space에서 realization을 허용하는지 판별하는 데 초점을 둔다. 이 survey는 기초 정의와 이론을 전개하면서 응용을 강조하며, 특히 NMR 데이터로부터 protein structure를 결정하는 문제를 중점적으로 다룬다.

1 서론: Distance Geometry는 Menger의 거리 기반 특성화에서 시작되어 Blumenthal 에 의해 이후 완성되었으며, distance matrix를 인식하는 subset problem을 포함한다.유클리드 거리의 경우, Cayley의 결과는 충분히 많은 점이 더 낮은 차원의 아핀 공간에 놓일 때 Cayley-Menger 행렬식이 영이 된다는 필요조건을 제시한다.
1 서론: Distance Geometry Problem은 weighted graph가 주어진 edge distance를 실현하는 mapping x: V → R^K를 허용하는지 묻는다.Realization은 이러한 mapping이며, subgraph의 realization은 전체 graph의 partial realization이다.
1 서론: DGP는 고전적 distance geometry를 sparse-distance positioning과 연결한다. sparse-distance positioning에서는 일부 object pair에 대해서만 측정한 값으로 지리적으로 분산된 object의 좌표를 추론한다 (Yemini,; [233]).응용 분야로는 molecular conformation, wireless sensor network, statics, data visualization, robotics가 있다.
1 서론: 이 survey는 응용 중심의 관점을 취하며, 특히 Nuclear Magnetic Resonance 데이터로부터 protein structure를 결정하는 문제에 초점을 둔다.NMR measurement는 distance interval로 직접 주어지는 것이 아니라 atom-type pair 사이의 거리에 대응하는 frequency reading으로 얻어진다.
1.1 기본 정의: 수학적 preliminaries에서는 survey 전반에서 사용하는 weighted graph, subgraph, path, cycle, chordality, minor, vertex order, realization 및 rigidity 관련 개념을 정의한다.또한 graph 기반 realization algorithm을 위해 PEO, DVOP, Henneberg type I order를 소개한다.

2 거리 기하학의 수학

이 절에서는 Cayley–Menger determinant, simplex orientation, exterior algebra, matrix characterization을 통해 Euclidean distance geometry를 전개한다. 또한 이러한 기초를 manifold, semidefinite programming, matrix completion과 연결한다.

Cayley–Menger determinant: Cayley–Menger determinant는 simplex volume과 oriented volume을 나타내며, 서로 반대인 부호는 하나의 facet을 공유하는 simplex의 두 orientation을 의미한다.이는 pairwise distance duv = ∥pu − pv∥를 사용하며 oriented matroid 와 연결된다.
Manifold: 곡면 manifold에서는 Gödel의 simplex condition 수정이 distance geometry를 확장하며, kissing number 및 coding theory와 연결되는 spherical realization을 포함한다.구면 결과는 네 점 집합이 영이 아닌 Cayley–Menger determinant를 가질 때 적용된다.
외대수: Cayley–Menger determinant는 외대수적 교대곱을 이루며, 영이 아닌 determinant는 선형 독립과 동치이고 관련 invariant는 chirotope 실현을 뒷받침한다.이 구성은 반복 벡터 곱을 x^2가 생성하는 ideal에서 영으로 식별하는 것에서 도출된다.
PSD와 matrix completion: Schoenberg의 bijection은 Euclidean distance matrix와 positive semidefinite matrix를 동치로 만든다. D는 R^K에서는 점을 나타내지만 R^(K−1)에서는 정확히 나타내지 못하며, 이는 x^⊤Ax가 rank K인 PSD일 때 성립한다.이 대응은 동치인 EDM 및 PSD matrix-completion 문제의 기반이 된다.

3 분자 구조

이 절에서는 distance geometry의 주요 응용 분야로서 분자 구조를 개관하며, NMR 데이터 해석과 연계된 inverse problem으로서의 역할을 강조하고 continuous, discrete, interval-distance 방법을 다룬다.

3 분자 구조: 분자 구조 연구는 주로 NMR 데이터 해석과 연계된 inverse problem으로 distance geometry를 활용하지만, 응용이 이 분야에만 국한되지는 않는다.이 절에서는 continuous search 방법, discrete search 방법, interval distance로의 확장, 최근 NMR 특화 결과를 다룬다.

3.1 테스트 인스턴스

테스트 인스턴스는 기하학적 구성, 물리적으로 동기 부여된 random 구성, dense PDB 구성, sparse PDB 구성으로 나뉘며, 측정값에 distance threshold가 있으므로 NMR에는 sparse PDB 데이터가 선호된다. 방법은 realization accuracy와 CPU time으로 비교하며, penalty, LDE, RMSD를 표준 accuracy measure로 사용한다.

테스트 인스턴스 선택: 테스트 인스턴스에는 grids 와 같은 geometrical models, physically motivated random models, dense PDB conformations [155, 3, 4], sparse PDB conformations [83, 122]이 포함된다.Dense PDB 인스턴스에는 residue 내부의 distance와 인접 residue까지의 distance가 포함되는 반면, sparse PDB 인스턴스에는 threshold 이내의 distance가 포함된다.
테스트 인스턴스 선택: Sparse PDB 인스턴스는 NMR이 주어진 threshold까지의 distance만 측정하므로 NMR testing에 가장 잘 부합한다.따라서 survey에서는 주로 sparse PDB test set을 사용하고, 때때로 geometric 및 hard random 인스턴스를 추가했으며, 쉬운 dense PDB 인스턴스는 피했다.
테스트 인스턴스 선택: Dense PDB 인스턴스는 residue가 세 개보다 많은 atom을 포함하므로 protein backbone 순서가 R3에서 3-trilateration order를 유도한다는 점에서 쉬운 것으로 간주된다.이러한 order를 갖는 graph는 효율적으로 realization할 수 있으므로, 도전적인 테스트 케이스로서의 유용성이 제한된다.
평가 척도: 방법은 일반적으로 생성하는 realization x의 accuracy와 speed를 accuracy measure 및 CPU time으로 비교한다.BP를 포함한 일부 방법은 추가로 valid realization의 전체 집합을 생성할 수 있다.
평가 척도: Penalty, Largest Distance Error (LDE), Root Mean Square Deviation (RMSD)는 널리 사용되는 세 가지 accuracy measure다.Penalty는 objective function을 평가하고, LDE는 penalty를 scaling한 평균 제곱근 값이며, RMSD는 optimal rotation과 translation을 적용한 뒤 centered point set을 비교한다. RMSD는 알려진 optimal configuration이 존재할 때 의미가 있다.

3.2 Molecular Distance Geometry Problem

Molecular Distance Geometry Problem (MDGP)은 DGP3와 동등하며, NMR로 측정한 불완전한 Euclidean distance로부터 R3 내 원자 위치를 복원해 분자 conformation을 모델링한다. 이 절에서는 global optimization, smoothing 기반 continuation, geometric build-up algorithm을 포함한 exact-distance 해법을 검토한다.

3.2 Molecular Distance Geometry Problem: MDGP는 원자를 vertex로, 관측된 원자 쌍 간 거리를 edge로 사용해 분자 구조, 즉 R3 내 상대적 원자 위치를 결정한다.NMR 실험은 짧은 Euclidean distance의 부분집합을 제공하며, MDGP는 이를 사용해 양립 가능한 분자 conformation을 복원한다.
3.2 Molecular Distance Geometry Problem: 수치적 해법은 어렵다. fsolve는 10개 미만의 vertex를 갖는 작은 weighted graph에서도 실패했으며, Couenne은 합리적인 시간 내에 |V| ∈ {2, 3, 4}인 instance만 처리했다.이 절에서는 global optimization을 nonnegative fourth-degree polynomial objective에 따른 squared infeasibility 최소화로 정식화하며, 이 objective의 값은 feasible realization에서 정확히 0이다.
3.2 Molecular Distance Geometry Problem: Gaussian-transform smoothing과 homotopy continuation은 local optima를 줄이고 효과적인 MDGP optimization을 지원한다. DGSOL은 small-to-medium instance에 효율적이며 interval distance로 자연스럽게 확장된다.DGSOL은 무료로 이용할 수 있고 cubical grid에서 성공적으로 테스트되었다. Figure 3은 DGSOL이 산출한 잘못된 1mbn conformation과 BP Alg. 1이 산출한 올바른 conformation을 대조한다.
3.2 Molecular Distance Geometry Problem: Geometric build-up algorithm은 네 개의 non-coplanar neighbor로부터 triangulation을 통해 vertex를 재구성하며, 필요한 조건이 성립하면 unique position을 산출한다.이 방법은 충분히 dense한 graph를 대상으로 설계되었으며, 관련 linear system이 unique solution을 가지므로 uniqueness가 따른다.
3.2 Molecular Distance Geometry Problem: Updated geometric build-up은 10개의 sparse PDB protein에서 수치 오차를 제어해 O(10^-8) to O(10^-13)의 RMSD를 달성했으며, complete rational graph는 linear-time O(n) 해법을 허용한다.Original geometric build-up method는 수치 오차에 매우 민감하다 [64]. 이에 따라 Wu and Wu 가 updated algorithm을 제안했다.

3.3 이산화 가능성 · 3.3.1 강체 기하 가설과 분자 그래프 · 3.3.2 Branch-and-Prune 알고리즘의 발전

이 절에서는 rigidity를 통해 discretizable DGP instance를 특성화하고, binary placement와 pruning을 활용하는 정확한 조합 탐색인 Branch-and-Prune을 전개한다. 또한 분자 그래프 구성과 protein-conformation 응용을 위한 BP의 발전을 설명한다.

3.3 이산화 가능성: Discretizability는 정확하고 효율적인 mixed-combinatorial 방법을 뒷받침하며, discretizable DGP instance의 모든 해를 찾는 exact algorithm을 포함한다.discretizability, rigidity, combinatorial search 사이의 관계에 초점을 둔다.
3.3 이산화 가능성: rigid graph에서는 realization set X가 finite인 반면, realization을 갖는 거의 모든 non-rigid graph는 uncountably many 해를 갖는다 [16, Thm. 2.2.1; 153].따라서 rigidity는 탐색 공간을 잠재적으로 uncountable한 공간에서 유한한 realization 집합으로 줄인다.
3.3 이산화 가능성: 첫 K vertex를 고정하면, non-uniquely rigid graph에서는 이후 각 vertex에 대해 두 placement가 가능하므로, 추가 edge가 실현 불가능한 branch를 prune하기 전에 |X| = 2^(n−K)가 된다.추가 edge는 후보 placement 중 하나 또는 둘 모두를 제거할 수 있다.
3.3.2 Branch-and-Prune 알고리즘의 발전: Protein-backbone realization은 전체 protein을 실현하기 위한 어려운 단계이므로 non-uniquely rigid graph의 동기를 제공하며, backbone ordering은 exact BP를 뒷받침할 수 있다.자연스러운 원자 순서를 활용해 exactness guarantee를 갖는 vertex order를 구성할 수 있다.
3.3.1 강체 기하 가설과 분자 그래프: 알려진 covalent bond length와 bond angle은 두 bond로 떨어진 원자 사이의 distance를 결정하며, bond graph를 molecular graph G2로 완성한다 [99].두 edge path가 원자를 연결할 때마다 completion 과정에서 weighted edge를 추가한다.
3.3.2 Branch-and-Prune 알고리즘의 발전: BP는 three-sphere intersections와 이론적으로 정당화된 vertex order를 결합한다. 2005년에 고안되고 검증된 뒤 2008년에 발표되었으며, 이후 정의된 DGP subclass에서 complete임이 증명되었다 [118, 124, 122, 159].후속 연구에서는 vertex ordering을 자동화하고, BP를 protein에 적용하며, 방법을 비교하고, backbone decomposition을 통해 tree size를 줄였다.

3.3.3 구면 교차와 확률 · 3.3.4 이산화 가능한 정점 순서 문제

구면 교차는 affine independence와 simplex inequality에 의해 좌우된다. 일반적으로 feasible intersection에는 두 점이 포함되며, 퇴화한 경우에는 0개, 1개 또는 비가산적으로 많은 점이 나온다. 이러한 사실은 DVOP를 정당화한다. DVOP는 실현 개수가 최대 2^(n−K)가 되도록 하는 순서를 찾으며, 일반적으로 NP-complete이지만 K가 고정되면 polynomial time에 해결된다.

3.3.3 구면 교차와 확률: 제곱거리로 표현되는 Simplex inequality ∆K(U) ≥ 0가 feasibility를 특징짓는다. 엄밀한 부등식은 두 교점이 존재함을 뜻한다 [115].Cayley-Menger determinant는 관련된 distance-based 조건을 제공하며, 구면 교차는 molecular modelling에서 상세히 다뤄진다.
3.3.3 구면 교차와 확률: CM(U−) = 0이면 구면 교차는 비가산적이며, ∆K(U, d) = 0이면 점 하나를 갖는다. 그 밖의 경우에는 점이 0개 또는 2개다 [115].중심들의 affine dimension이 K−1보다 작으면 교차는 비가산적이다. 그렇지 않으면 그 cardinality는 {0, 1, 2}에 속한다.
3.3.3 구면 교차와 확률: 확률 1로, affinely independent한 중심을 갖는 K개 구의 nonempty intersection은 정확히 두 점을 갖는다. 0점 및 1점인 경우는 measure-zero 퇴화다.순서에서 적어도 K개의 adjacent predecessor가 존재하면 infeasibility로 인해 실현 개수가 최대 2^(n−K)까지 줄어들 수 있다.
3.3.4 이산화 가능한 정점 순서 문제: 각 후속 정점이 정확히 K개의 adjacent predecessor를 갖는 valid vertex order는 확률 1로 |X| = 2^(n−K)를 산출한다.적어도 K개의 adjacent predecessor가 있으면 후보 위치 중 하나 또는 둘 모두가 추가 거리를 위반할 수 있으므로 |X|가 더 작아질 수 있다.
3.3.4 이산화 가능한 정점 순서 문제: DVOP는 처음 K개 정점이 K-clique를 이루고 이후의 모든 정점이 적어도 K개의 adjacent predecessor를 갖는 순서를 찾으며, 이를 통해 초기 realization의 유일성을 보장한다.discretizable distance geometry problem에서는 처음 K개 정점의 realization을 알고 있어야 하므로 이 정점들이 clique를 유도해야 한다.
3.3.4 이산화 가능한 정점 순서 문제: DVOP는 NP-complete이지만, K-subset을 열거하고 유망한 clique를 greedy하게 확장하면 O(n^(K+3)) 알고리즘을 얻을 수 있으므로 K가 고정되면 polynomial time이다.알고리즘은 이용 가능한 adjacent predecessor의 최대 개수가 K보다 작아지면 중단된다.
3.3.4 이산화 가능한 정점 순서 문제: DVOP preprocessing은 backbone order가 DVOP order가 아닌 sparse PDB instance를 때때로 해결할 수 있으며, 특히 distance threshold가 6Å가 아니라 5.5Å일 때 그렇다.보고된 computational result는 이 효과를 usual threshold보다 낮은 threshold를 사용하는 것과 연결한다.

3.3.5 이산화 가능한 거리 기하 문제

이산화 가능한 거리 기하 문제(DDGP)는 가중 그래프, 차원 매개변수 K, 정점 순서, 초기 realization을 지정한 뒤 해당 realization이 유효하게 확장될 수 있는지 묻는다 [115]. 구조적 조건은 순차적 realization을 가능하게 하며, DDGP 방법은 선험적 특성화가 없는 더 넓은 인스턴스도 해결할 수 있다.

문제 정의: DDGP 입력은 가중 무방향 그래프, 정수 K > 0, 정렬된 정점 집합, 첫 K개 정점의 유효한 realization으로 구성된다.첫 K개 이후의 각 정점은 인접한 선행 정점을 최소 K개 가진다.
문제 정의: 첫 K개 이후의 모든 정점에 대해, K개의 인접한 선행 정점은 clique를 이루며 strict triangular inequalities ∆K−1(Uv, d) > 0을 만족한다.이 조건들은 순차적 realization에 사용되는 선행 정점 부분집합 Uv를 정의한다.
문제 정의: DDGP는 초기 realization을 그래프의 유효한 realization으로 확장할 수 있는지 묻고, 고정 차원 변형인 DDGPK와 DDGP3가 [159]에서 논의된다.일반 결정 문제는 [115]에서 다룬다.
범위와 한계: DDGP 방법은 선행자 부분 그래프가 graph clique가 아닌 경우에도 추가 인스턴스를 해결할 수 있다. 계산 과정에서 현재 realization이 ∆K−1(Uv, d)를 well defined하게 만들 수 있기 때문이다.이처럼 더 폭넓은 인스턴스에 대한 선험적 특성화는 현재 이용 가능하지 않다.

3.3.6 Branch-and-Prune 알고리즘

Branch-and-Prune 알고리즘은 구면 교집합에서 분기하고 실현 불가능한 후보를 가지치기하여 유효한 realization을 재귀적으로 열거한다. 모든 비합동 realization 또는 단일 realization을 찾을 수 있으며, sparse PDB instance에서 높은 효율성과 신뢰성을 보인다.

Branch-and-Prune 알고리즘: BP는 최대 두 개의 구면 교집합 후보로 분기하며, 회전과 평행이동을 법으로 하는 유효한 realization의 완전한 집합 X를 찾는다.알고리즘은 BP(K + 1, x̄, ∅)를 호출하여 초기화한다.
Branch-and-Prune 알고리즘: 각 realization은 이진 수열 χ(x)로 부호화할 수 있으며, 각 vertex를 포함하는 predecessor embedding을 지나는 초평면의 어느 쪽에 해당 vertex가 놓이는지를 부호가 나타낸다. 이를 chirality 라고 한다.처음 K개의 항은 1로 고정되며, 0인 경우의 확률은 0이다.
Branch-and-Prune 알고리즘: BP는 모든 유효한 realization을 얻을 때까지 종료까지 실행하거나, 첫 번째 leaf에서 중단하여 하나의 realization을 얻을 수 있으며, 효율성과 신뢰성에서 테스트한 대부분의 continuous-search 알고리즘보다 우수하다.이 대목은 저자들이 아는 한 BP가 유일한 방법이라고 특징짓는다…
Branch-and-Prune 알고리즘: 25개의 sparse PDB instance에서 완전한 realization 집합이 도출되었으며, 각 집합에는 RMSD가 최악의 경우 O(10−6)인 realization 하나와 LDE가 최악의 경우 O(10−7)인 isomer들이 포함되었고, 총 user CPU time은 5.87s였다.instance의 범위는 n = 57, m = 476에서 n = 3861, m = 35028까지였으며, 한 outlier가 전체 시간의 90%를 소모했다.
Branch-and-Prune 알고리즘: Pruning edge는 Direct Distance Feasibility를 통해 BP search tree를 축소하며, 두 개 대신 후보를 0개 또는 1개만 남길 수 있다.Discretization edge는 instance가 DDGP에 속하도록 보장하고, pruning edge는 해당 distance와의 compatibility를 검사한다.

3.3.7 Dual Branch-and-Prune

Dual branch-and-prune은 최대 두 개의 missing distance를 분기하고 clique를 따라 진행하면서 비유클리드 completion을 가지치기해 partial Euclidean distance matrix를 완성한다. weighted graph와 partial symmetric matrix 사이의 대응을 통해 primal branch-and-prune과 dual을 이루며, Theorem 3.1 ([137])에 의해 complete하다.

3.3.7 Dual Branch-and-Prune: Dual branch-and-prune은 primal branch-and-prune의 matrix-completion counterpart이며, weighted graph와 partial symmetric matrix 사이의 선형 시간 매핑으로 연결된다.Primal method는 point realization을 선택하는 반면, dual method는 missing distance를 선택한다.
3.3.7 Dual Branch-and-Prune: 각 단계에서 dual branch-and-prune은 K+2-vertex near-clique의 Cayley–Menger equation을 사용해 missing distance를 할당한다.Partial matrix가 distance matrix이면 이 equation은 최대 두 개의 실수 candidate value를 가지며, Euclidean completion이 없으면 candidate가 없다.
3.3.7 Dual Branch-and-Prune: Missing distance에 두 개의 feasible value가 있을 때 method는 분기하고, full clique를 따라 진행하며, Euclidean completion이 없는 branch를 prunes한다.하나의 missing edge를 가진 near-clique는 일반적으로 R^K에서 두 개의 realization을 산출하는 반면, full clique는 branching이 필요하지 않다.
3.3.7 Dual Branch-and-Prune: Dual branch-and-prune은 입력 partial distance matrix의 all possible completions를 반환한다.Theorem 3.1 ([137])은 Algorithm 2에 대해 이 completeness guarantee를 확립한다.
3.3.7 Dual Branch-and-Prune: Primal branch-and-prune과 달리 dual method는 initial (K+1)-clique를 필요로 한다. Complete distance matrix는 reflected realization 두 개를 나타내기 때문이다.Primal method는 initial K-clique만 필요로 한다.

3.3.8 이산화 가능한 분자 거리 기하 문제

DMDGP는 각 vertex의 predecessor를 K개의 immediate predecessors로 제한하며, 이는 protein-backbone realization에 의해 동기가 부여되고 symmetry, tractability, complexity에 관한 이론적 결과를 가능하게 한다. 또한 torsion-angle cosine에 기반한 mathematical-programming formulation을 허용한다.

정의와 동기: DMDGP는 각 vertex의 K개 predecessor가 DDGP의 임의의 predecessor와 달리 immediate predecessors여야 한다고 요구하며, 임의의 K에 대해 KDMDGP로 일반화된다.discretization edge는 |u − v| ≤ K를 만족하며, x(Uv) = {xv−K, . . . , xv−1}이다.
정의와 동기: Protein molecular structure는 각 vertex v > 3에 대해 두 개의 immediate predecessors를 보장하지만, 이는 K = 2일 때에만 discretizability를 직접 보장한다.추가적인 protein property를 이용하면 DMDGP 정의를 만족하는 다른 vertex order를 얻을 수 있다.
이론적 결과: Immediate-predecessor structure는 X의 symmetry 결과와 NMR data를 사용하는 protein-backbone KDMDGP에 대한 BP algorithm의 fixed-parameter tractability를 뒷받침한다.DMDGP는 Subset-Sum [122]으로부터의 reduction을 통해 NP-hard이며, 이 결과는 KDMDGP 으로 일반화된다.
Mathematical-programming formulation: Mathematical-programming formulation은 torsion angles φv를 사용해 각 선택을 모델링하며, 그 input cosine cv는 인접한 plane-normal scalar product를 제한한다.v > 3에 대해 formulation은 αv−1(x) · αv(x) = ∥αv−1(x)∥∥αv(x)∥cv를 부과하며, fixed-K generalization에는 Graßmann-Plücker relations 을 사용한다.

3.3.9 해집합의 대칭성

KDMDGP 인스턴스에서는 partial reflection이 해집합에 추이적으로 작용하는 Abelian symmetry group을 이루며, 확률 1로 |X|가 2의 거듭제곱임을 보인다. 이러한 대칭성은 한 해를 찾은 뒤 모든 realization을 생성하여 BP도 가속한다.

3.3.9 해집합의 대칭성: 초기 실험에서는 protein 및 protein-like 인스턴스에 대해 2의 거듭제곱이 관찰되었지만, 구성된 한 인스턴스는 54개의 해를 가졌고, 확률 1 정리는 반례의 무한 가산 class를 허용한다 [122, 145].이 결과는 경험적 conjecture를 설명하는 동시에 partial reflection 이론의 토대를 제공한다.
3.3.9 해집합의 대칭성: 각 BP branching pair는 K개의 immediate predecessor가 정의하는 hyperplane을 통한 reflection으로 서로 연결된 realization들로 구성된다.이러한 partial reflection은 확률 1로 injective하고 idempotent이며, 그 작용은 chirality transformation에 대응한다.
3.3.9 해집합의 대칭성: 확률 1로 discretization group은 C_2^(n−K)와 동형인 Abelian group이며, X에 대한 작용은 추이적이다.그 generator는 서로 commute하는 partial reflection으로, discretization-edge distance를 보존하고 모든 realization을 연결한다.
3.3.9 해집합의 대칭성: 확률 1로 pruning group은 X에 추이적으로 작용하며, 이는 어떤 정수 ℓ에 대해 |X| = 2^ℓ임을 뜻한다.증명에서는 pruning group을 discretization group의 subgroup으로 취급하며, 그 order는 2의 거듭제곱이다.
3.3.9 해집합의 대칭성: 경험적으로 BP가 하나의 유효한 realization을 찾으면, group generator가 rotation과 translation을 제외한 다른 모든 realization을 생성하여 CPU time을 대략 2/|X|로 줄인다 [157, 158].첫 번째 유효한 realization이 식별되면 generator를 사용할 수 있으며, factor 2는 BP에 이미 존재하는 reflection symmetry를 반영한다.

3.3.10 고정 매개변수 다루기 쉬움

이 논문은 단백질 인스턴스에서 BP 알고리즘이 고정 매개변수 다루기 쉬움과 다항식 실행 시간을 갖도록 하는 충분한 가지치기 간선 조건을 확립한다. 실험적으로 PDB 단백질 45개 중 40개는 한 조건을, 5개는 다른 조건을 만족하며, 모두 v0 = 4이다.

3.3.10 고정 매개변수 다루기 쉬움: 충분히 뒤쪽에 있는 정점들이 앞쪽 정점들로부터 가지치기 간선을 가지면, Proposition 3.9는 BP 탐색 트리의 너비를 2^(v0−K)로 제한한다.이 조건은 모든 v > v0에 대해 u < v − K를 만족하면서 가지치기 간선 {u, v}를 갖는 어떤 v0 > K가 존재할 것을 요구한다.
3.3.10 고정 매개변수 다루기 쉬움: 긴 가지치기 간선 부재 부분수열 앞에 적절한 가지치기 간선이 놓이면, Proposition 3.10 역시 BP 탐색 트리의 너비를 2^(v0−K)로 제한한다.각 조건을 만족하는 선행 정점은 충분한 분리 조건과 입사 가지치기 간선을 모두 만족해야 한다.
3.3.10 고정 매개변수 다루기 쉬움: 첫 두 조건하에서 T를 계산할 때 복잡도가 일반적으로 n에 대해 상수라면, BP의 최악 실행 시간은 O(2^v0 n)이다 [140].일반적인 너비 상한은 O(2^v0 log n)이며, L을 상수로 보기 전에는 O(2^v0 L^2 log n) = O(Ln)을 얻는다.
3.3.10 고정 매개변수 다루기 쉬움: 로그 개수만큼의 예외적인 2의 거듭제곱 레벨을 허용하는 더 약한 조건에서는 레벨 n에서의 너비가 2^v0 n으로 제한되고 실행 시간은 O(2^v0 n^2)이다.이에 대응하는 가지치기 간선 경로는 해당 예외 레벨을 제외하면 대각선을 따르며, 예외 레벨에서는 탐색 노드 수가 두 배가 된다.
3.3.10 고정 매개변수 다루기 쉬움: PDB 단백질 인스턴스 45개 중 40개는 Proposition 3.9를 만족하고 5개는 Proposition 3.10을 만족하며, 모두 v0 = 4로 선형 경험적 복잡도를 뒷받침한다 [140, 122].이 결과는 BP가 실제 단백질에서 다항식, 구체적으로 선형 복잡도를 보인다는 계산적 증거와 일치한다.

3.4 구간 데이터

구간 거리 기하학은 불확실한 NMR 측정값을 거리 구간으로 모델링하고, 비선형 부등식 제약을 만족하는 embedding을 찾는다. 이 절에서는 이 문제를 위한 smoothing, projection, basin-hopping, multilevel, stochastic 방법을 살펴본다.

구간 데이터는 NMR 측정 불확실성을 나타내며, 지정된 거리를 embedding이 비선형 부등식을 통해 만족해야 하는 실수값 범위로 변환한다.구간 정식화는 정확한 edge distance를 [dL, dU] 구간으로 대체한다.
다른 접근법은 smoothing 방법을 적용하거나, EMBED 에서 matrix decomposition 전에 bound를 완성하고 정제하거나, monotonic basin hopping 과 multilevel local NLP search를 사용한다.이 방법들은 bound refinement, local optimization, structured search를 서로 다르게 조합해 구간 정식화를 다룬다.
Hyperbolic smoothing 은 summand의 형태를 일치시켜 computational result를 개선하지만, near-cubic grid arrangement에서 가장 잘 작동한다.그 algorithm은 DGSOL과 유사하지만, problem-specific smoothing을 사용하므로 general-purpose Gaussian smoothing과 구별된다.
Alternating projection은 무작위로 초기화한 pre-distance matrix를 negative-semidefinite 및 zero-diagonal convex set에 반복적으로 projection하여 Euclidean distance matrix를 찾는다.최악의 경우 수렴에 무한히 많은 iteration이 필요할 수 있지만, empirical test는 588-atom protein을 포함해 APA iteration 다섯 번이면 충분함을 시사한다.
Stochastic Proximity Embedding 은 interval constraint가 위반되면 atom pair를 무작위로 이동하지만, 모든 constraint를 만족한다는 no guarantee를 제공하지 않는다.그럼에도 의 보고된 “success stories”는 이를 유효한 methodology로 뒷받침한다.

3.5 NMR 데이터

NMR 실험은 주로 수소 쌍에 대한 불완전한 구간값 거리 정보를 제공하지만, 모호성과 실험 오차로 신뢰성이 제한된다. Protein-specific re-orders와 interval branch-and-prune 방법은 화학적으로 알려진 거리를 이산화에 사용하고, NMR 구간은 주로 pruning에 활용한다.

NMR 측정: NMR 데이터는 선택된 원자 쌍, 대부분 수소 원자 쌍의 거리를 추정하지만, 구별할 수 없는 원자에는 pseudo-atoms와 점진적으로 확장되는 upper bounds가 필요하다.분자 불안정성, 기기 잡음, spin diffusion도 신호에 영향을 줄 수 있으며, 관측값을 조작하는 과정에서 interval-type errors가 발생한다 [17].
NMR 측정: 알려진 분자 조성은 NMR에 공유 결합 거리, 두 결합 거리, 원자 식별 정보를 보완하여 chemically informed distance-geometry models를 가능하게 한다.NMR 관측값은 일반적으로 ({a, b}, d, q) 형태의 triplets로 표현되며, 오차가 발생하기 쉬운 처리 후에는 정확한 거리가 구간으로 대체된다.
Re-orders: Re-orders는 수소 원자, 반복 원자, torsion-angle intervals를 대체하는 유한 candidate sets를 활용하여 신뢰하기 어려운 비수소 NMR 거리를 처리한다.이를 통해 valence가 2보다 큰 원자도 여러 bond lengths에 기여할 수 있고, 정밀도 손실 없이 torsion에서 유도된 구간을 촘촘하게 이산화할 수 있다.
Interval BP: Interval BP algorithm은 거리 제약을 교차시킬 때 sphere를 spherical shells로 대체하면서도 interval data에 대한 branching과 pruning 단계를 유지한다.3차원에서는 두 sphere와 하나의 spherical shell을 교차시키면 확률 1로 서로 분리된 두 곡선이 얻어진다.
Interval BP: Re-orders를 사용하면 정밀한 화학적 유도 거리가 이산화를 수행하고 NMR 구간은 pruning에만 사용되어, 최대 2D subnodes를 갖는 search-tree nodes가 생성된다.따라서 이산화 가능한 구간을 기준으로 branching할 때 search tree는 더 이상 binary가 아니다.
Protein side chains: 모든 20개 아미노산에서 side chains가 복잡하고 잠재적으로 큰 구조를 가지므로, complete protein conformations에 이산화를 적용하는 일은 여전히 어렵다.그럼에도 side chains는 protein conformations를 식별하는 데 중요하다.

4 공학적 응용

distance geometry의 공학적 응용에는 무선 sensor network localization, statics, data visualization, robotics가 포함된다. 제공된 자료는 global rigidity, unique localizability, scalable SDP 기반 formulation을 통한 localization을 중점적으로 다룬다.

4.1 무선 네트워크: 무선 sensor network localization은 통신 신호 라우팅에 필요한 위치를 복원하기 위해 센서 간 거리 추정값을 사용한다.관련 환경은 일반적으로 R^2 또는 R^3이며, 다층 건물과 산악 지역을 포함한다.
4.1 무선 네트워크: Global rigidity는 그래프가 congruence까지 유일한 realization을 갖는다는 뜻이며, 센서 위치가 유일하게 복원 가능한 조건을 결정한다.K=2인 경우 global rigidity는 2- 또는 3-clique 경우, 또는 3-connectivity와 redundant rigidity로 특성화된다.
4.1 무선 네트워크: K-unique localizability는 R^K 및 더 높은 차원에서 uniqueness가 성립하고 anchor가 global rigidity를 보장할 때 SDP duality를 통해 정확한 polynomial-time realization을 가능하게 한다.anchor subgraph는 generically globally rigid해야 하며 최소 K + 1개의 anchor를 포함해야 한다. 정확한 algorithm은 에 기술되어 있다.
4.1 무선 네트워크: SDP method는 distance geometry를 semidefinite feasibility와 연결하고 interval-valued, imprecise distances를 수용할 수 있기 때문에 최근 무선 localization 접근법을 주도한다.Facial reduction과 vertex clustering은 clique를 식별하고 K-trilateration order를 통해 이를 확장함으로써 SDP scaling을 개선한다.
4.1 무선 네트워크: SOCP relaxation은 SDP relaxation의 500개에 비해 4000개 vertex까지 scaling되며, 더 강한 ESDP relaxation도 유사한 scaling을 보인다.SOCP constraint는 ∥w_uv∥2 = y_uv를 ∥w_uv∥2 ≤ y_uv로 완화한다. Tseng은 이를 포기하고 ESDP를 채택했다.
4.2 Statics와 rigidity: R^2에서 Laman의 characterization은 |E| = 2|V|−3이고 모든 subgraph에 대해 |E′| ≤ 2|V′|−3인 rigid graph를 제시하지만, K > 2에 대해서는 완전한 characterization이 알려져 있지 않다.Generic framework 전반에서 rigidity와 infinitesimal rigidity가 일치하므로, 거의 모든 경우 rigidity를 graph property로 다룰 수 있다 [7, 8].

5 결론

Euclidean distance geometry는 생물학, 통계학, 공학에서 중요한 응용 분야를 갖춘 성숙하고 광범위한 분야다. 최근 확장 연구는 부분 distance function으로부터 distance space를 결정하는 inverse problem을 다루며, 수학적·응용적 관심을 더한다.

Euclidean distance geometry는 생물학, 통계학, 공학에서 중요한 응용 분야를 갖는다.
이론적 토대는 약 한 세기 전 Cayley, Menger, Schoenberg, Blumenthal, Gödel에 의해 확립됐다.
최근 확장 연구는 부분 distance function으로부터 distance space를 결정하는 inverse problem을 다룬다.이러한 확장 연구는 이 분야에 수학적·응용적 관심을 더한다.