그래픽 시간 왜곡

그래픽 시간 왜곡(GTW)은 여러 쌍의 시계열 또는 ^[1]시퀀스를 공동으로 정렬하기 위한 프레임워크입니다.GTW는 각 시퀀스 쌍의 정렬 정확도와 쌍 간의 유사성을 모두 고려합니다.반대로 동적 시간 왜곡(DTW)을 사용한 정렬은 쌍을 독립적으로 고려하고 주어진 쌍에서 두 시퀀스 사이의 거리만 최소화합니다.따라서 GTW는 DTW를 일반화하고 쌍 간 유사성이 예상될 때 더 나은 정렬 성능을 달성할 수 있습니다.

GTW의 한 가지 응용 프로그램은 인접 픽셀의 전파 패턴이 일반적으로 유사한 시간 경과 생체 이미징 데이터의 신호 전파 분석입니다.다른 응용 프로그램에는 서명 식별, 쌍안 스테레오 깊이 계산 및 프로테오믹스 데이터 ^[2]분석의 LC-MS 프로파일 정렬이 포함됩니다.실제로, 데이터가 상호 의존적인 시계열/시퀀스로 구성되어 있는 한 GTW로 분석할 수 있습니다.

GTW는 DTW 등가 최단 경로 문제를 이중 그래프의 최대 흐름 문제로 변환하여 뒤틀린 경로 간의 제약 조건 또는 유사성을 모델링할 수 있으며, 이는 대부분의 최대 흐름 알고리듬으로 해결할 수 있습니다.그러나 데이터가 크면 이러한 알고리즘은 시간이 많이 걸리고 메모리 사용량이 많습니다.GTW 문제를 해결하기 위해 효율적인 알고리듬인 BILCO(^[3]Linear Component Operations)가 개발되었습니다.GTW 애플리케이션의 최첨단 일반 최대 흐름 알고리듬과 비교하여 계산 및 메모리 사용량 모두에서 평균 10배 향상을 달성할 수 있습니다.

조인트 정렬 및 GTW 공식화

이음매 정렬

$N개의$ 쌍 {( $\{(x_{n},y_{n})|n=1,2,...,N\}$ $\{(x_{n},y_{n})|n=1,2,...,N\}$ n $=$ 1 $\{(x_{n},y_{n})|n=1,2,...,N\}$ $\{(x_{n},y_{n})|n=1,2,...,N\}$ $\{(x_{n},y_{n})|n=1,2,...,N\}$ $N}$ {\ $\{(x_{n},y_{n})|n=1,2,...,N\}$ $\{(x_{n$ }, $y_{n}$ n $=1, 2,$ ..., $N$ 이 $있고$ ${x_{n},y_{n}}$ , 각 쌍 ${x_{n},y_{n}}$ ${x_{n},y_{n}}$ ${\$ $displaystyle$ ${x_{n$ }, $y_$ ${n$ 에 해당하는 $P_{n}$ 경로 PN이 있다고 가정합니다.일부 뒤틀림 경로 쌍은 유사한 것으로 알려져 있으며, 이러한 모든 쌍의 집합은 ( $){$ 로 ${(m,n)}$ 표시됩니다. 예를 들어, ( $){$ $displaystyle$ $(m, n)}$ 가 $(m,n)$ 이 집합에 있는 $(m,n)$ 경우 $P_{m}$ $P_{m}$ Pm $({$ 및 $({n})$ 은 $P_{n}$ 유사합니다.정렬된 시계열과 뒤틀린 경로 거리 사이의 유사성을 모두 최적화하기 위해 조인트 정렬 문제는 최소화 문제로 공식화됩니다.

$\displaystyle \min _{\{P_{n} n=1,2,...,N\}\left(\sum _{n=1}^{N} 비용(P_{n})+\kappa \sum _{(m,n)\in Neib} dist(P_{m,P_{n}\right)}$

$cost(P_{n})$ 서 $)$ {{ $displaystyle$ cost $(P_{n})}$ 는 $cost(P_{n})$ 뒤틀림 $P_{n}$ $P_{n}$ {{ $displaystyle P_{n$ $dist(P_{m},P_{n})$ ( ${m},$ ) {\ $displaystyle$ dist ( $P_{$ m})와 $y_{n}$ 한 후 x $x_{n}$ ${{$ $displaystyle$ $x_{n}$ 와 $x_{n}$ $y_{n}$ ${n$ $dist(P_{m},P_{n})$ $x_{n}$ 의 거리를 나타냅니다. $P_{n}}$ 은 $dist(P_{m},P_{n})$ $($ 는) $P_{displaystyle$ $P_{m}$ P_ $P_{m}$ $P_{m}$ { $P_{n}$ $}$ 및 $Pn{displaystyle$ P_ $P_{n}$ { $n$ $P_{n}$ 에 $P_{m}$ 경계되는 영역의 면적에 의해 정의되는 뒤틀림 $P_{m}$ ${$ m} $P_{n}$ $P_{n}$ ${$ $displaystyle P_$ ${n}$ 사이의 거리입니다.그리고 $\kappa$ \ $kappa}$ 는 $\kappa$ 시계열 정렬 비용 항과 뒤틀림 함수 거리 항 사이의 균형을 이루는 하이퍼 파라미터입니다.

유사성 강도는 응용프로그램별 또는 사용자가 설계한 것일 수 있습니다.관련된 서로 다른 뒤틀림 경로 쌍 $n$ ) {\ $displaystyle(m,$ n $(m,n)$ 에 대해 서로 다른 매개 변수 $\kappa _{(}m,n)$ $\kappa$ ( $)$ {\ $displaystyle$ \ $kappa_{(m, n$ 을 설정할 수 있습니다. 여기서는 단순화를 위해 통합된 하이퍼 매개 변수 $\kappa$ κ{\ $displaystyle \kappa$ 를 사용합니다.

위의 최소화 문제는 직관적으로 공식화됩니다.그러나 원래 형태로 효율적으로 해결하는 방법은 명확하지 않으며, 뒤틀림 경로의 순진한 열거는 NP-hard 문제로 이어집니다.

GTW 공식화

GTW 그래프 구성.첫 번째 행은 GTW 하위 그래프의 최소 컷이 DTW 그래프의 최단 경로와 최적의 뒤틀림 경로로 이중인 하나의 시계열 쌍에서 GTW 하위 그래프를 구성하는 프로세스를 보여줍니다.두 번째 행은 관련 시계열 쌍 사이에 교차 에지를 추가하는 과정을 보여줍니다. 교차 에지는 녹색으로 표시됩니다.인접한 뒤틀림 경로 사이의 면적 크기는 교차 에지 사이에서 절단된 에지 수에 비례합니다.

이 최소화 문제는 최소 절단과 뒤틀림 경로가 ^[1]동일한 GTW 그래프라는 특수 그래프에서 최소 절단 문제로 재구성될 수 있습니다.공식은 다음과 같이 설명할 수 있습니다.

$n_{t}h$ ${{displaystyle n_{t}h}$ 개의 $n_{t}h$ 시계열 쌍에 대해 DTW 그래프를 구성합니다.그런 다음 이 DTW 그래프를 GTW 하위 $G^{n}$ $({{$ 이라는 이중 그래프로 변환합니다. 역 에지의 용량을 무한으로 설정합니다.
각 유사한 $P_{m}$ 경로 쌍 $P_{m}$ ({ $displaystyle$ $P_{$ $P_{n}$ }) $P_{n}$ $Pn({$ n $P_{n}$ 에 대해 $({$ G $^{m})$ $G^{n}$ $({$ G $^{n})$ 에서 $G^{n}$ 동일한 위치의 노드를 용량 $\kappa /2$ / $({displaystyle \kappa/2$ 의 양방향 에지로 연결합니다.이러한 모서리를 교차 모서리라고 합니다.
그림과 같이 구성된 GTW 그래프는 N ${displaystyle$ N $}$ GTW $N$ 하위 그래프와 교차 에지로 $N$ 됩니다.
최대 흐름 알고리즘을 사용하여 생성된 그래프의 최소 컷을 얻습니다.각 GTW 하위 그래프 내의 최소 절단은 하나의 뒤틀림 경로에 해당합니다.

동등성에 대한 설명

각 GTW 하위 $G^{n}$ $({$ G $^{n}})$ 은 $G^{n}$ 단일 시계열 쌍의 정렬을 나타내는 DTW 그래프의 이중 그래프입니다.결과적으로, GTW 하위 그래프 내의 절단은 DTW 그래프 내의 뒤틀림 경로와 이중이며, 종단 정렬 비용 항은 하위 그래프 내의 절단 비용으로 나타낼 수 있습니다.역 에지의 무한 용량은 뒤틀림 경로의 단조로움과 연속성을 보장하는 데 사용됩니다.

교차 에지는 뒤틀림 경로의 유사성을 제한하고 목적 함수의 거리 항에 기여합니다.최소 절단 문제에서 노드는 결국 소스 측 또는 싱크 측에 할당되며, 최종 절단은 두 변 사이의 가장자리로 정의됩니다. $({$ G $^{m})$ 과 $G^{m}$ $({$ G $^{n})$ 의 $G^{n}$ 각 쌍은 $({m})$ 과 $P_m$ $P_{n}$ $({n})$ $P_{m}$ 의 거리에 기여하며 추가 $\kappa /2$ / $({displaystyle \kappa / 2$ }) 비용이 $\kappa /2$ 발생합니다.따라서 거리 항은 교차 모서리의 절단 비용으로 나타낼 수 있습니다.

따라서 GTW 그래프의 비용 절감은 목적 함수의 비용 항에 해당합니다.각 하위 그래프 내의 절단이 하나의 시계열 쌍의 뒤틀림 경로에 해당한다는 사실을 상기하면, GTW 그래프의 최소 절단은 조인트 정렬에서 뒤틀림 경로의 최적 솔루션에 해당합니다.

확장

인접한 복합 특정 그래픽 시간 왜곡(ncGTW)

다중 시퀀스 정렬의 목적은 모든 시퀀스를 공통 참조에 정렬하는 것입니다.그러나 이 일반적인 참조는 일반적으로 알려져 있지 않습니다.또한 시퀀스 중에는 구조 정보도 있습니다.GTW를 이러한 애플리케이션에 직접 적용할 수는 없지만, 이 문제를 해결하기 위해 GTW에 ncGTW라는 2단계 프레임워크를 구축했습니다.첫 번째 단계에서, 시퀀스들 사이의 사전 구조적 지식은 뒤틀림 기능을 얻기 위해 사용됩니다.두 번째 단계에서 이러한 뒤틀림 함수는 명시적으로 지정할 필요가 없는 가상 참조에 모든 시퀀스를 공동으로 정렬하는 데 도움이 됩니다.ncGTW는 프로테오믹스 데이터의 LC-MS 프로파일 정렬 문제에 적용되었으며 기존 ^[2]접근 방식보다 더 나은 성능을 보였습니다.

효율적 알고리즘

선형 구성요소 운영(BILCO)을 통한 양방향 푸시

기존의 최대 흐름 알고리즘을 통해 GTW 그래프의 최소 컷 문제를 해결하면 그래프 크기가 커서 실행 시간이 오래 걸리고 메모리 사용량이 많아 GTW 사용이 제한됩니다.BILCO 알고리듬은 관절 정렬 문제의 두 가지 중요한 특성을 활용하고 실행 시간과 메모리 사용량 모두에서 평균 10배 향상을 달성합니다.두 가지 속성은 다음과 같습니다.

조인트 정렬 문제는 쌍별 정렬의 일반화이며 GTW 그래프에 포함된 수많은 DTW 문제가 있습니다.각 GTW 하위 그래프는 DTW 그래프와 이중이므로 동적 프로그래밍을 통해 각 GTW 하위 그래프 내의 최대 흐름을 선형 시간으로 해결할 수 있습니다.
많은 애플리케이션에서 뒤틀림 경로의 대략적인 솔루션을 추정할 수 있으며, 이는 해결 프로세스를 가속화하는 초기화 역할을 할 수 있습니다.

최대 흐름 문제는 연결된 물 탱크에서 물을 펌핑하는 것과 유사합니다.각 GTW 하위 그래프는 물탱크이며 흐름은 물 흐름일 뿐입니다.이 알고리즘은 최대 유량에 도달할 때까지 Drain 운전(물탱크에서 물을 빼냄) 및 Discharge 운전(인접한 물탱크 간 물 교환)을 반복적으로 작동합니다.

첫 번째 속성에 따르면, BILCO는 흐름 교환을 (1) GTW 하위 그래프 내의 흐름 교환과 (2) 관련된 GTW 하위 그래프 간의 흐름 교환의 두 가지 유형으로 나눕니다.이 과정은 연결된 수조에서 물을 펌핑하는 과정과 유사할 수 있으며, 두 가지 유형의 흐름 교환을 배수 및 배출이라고 합니다.이러한 속성을 완전히 활용하기 위해 단일 노드가 아닌 구성 요소(각 구성 요소는 GTW 하위 그래프의 연결된 하위 집합)가 운영 단위로 사용됩니다.배출 및 배출 구성 요소 작업을 모두 선형 시간 내에 구현할 수 있습니다.

두 번째 속성은 양방향 푸시 전략에 영감을 줍니다.이 전략에서 BILCO는 먼저 초기 근사 솔루션을 사용하여 그래프를 두 부분으로 분할한 다음 얻은 싱크/소스 부분에서 초과/적자를 각각 밀어냅니다.기존의 푸시 라벨 기반 최대 흐름 알고리듬과 비교하여, BILCO는 중복 계산을 크게 줄입니다.이러한 전략은 다른 푸시 라벨 기반 알고리듬을 ^[3]가속화하는 데에도 활용될 수 있다는 점에 주목할 필요가 있습니다.

적용들

신호 전파 분석

시간 경과 생체 영상 데이터에서 신호 전파는 많은 세포 ^[4]유형에서 널리 관찰되는 현상입니다.신호 전파를 연구하는 것은 정상 및 병리학적 조건에서 이러한 세포의 기능을 밝혀내는 데 도움이 될 수 있습니다.전파 정보는 픽셀의 곡선을 기준 신호와 정렬하여 뒤틀린 경로에서 파생될 수 있습니다.생체 영상 데이터의 신호 대 잡음비가 낮기 때문에 쌍별 정렬 방법은 일반적으로 만족스럽지 못한 결과를 초래합니다.신호의 공간적 상관관계를 고려하여 인접 픽셀 간 뒤틀림 경로의 유사성을 GTW에서 활용하여 정렬 성능을 향상시킬 수 있으며, 이는 전파 특성을 보다 정확하게 계산할 수 있습니다.

깊이추출

쌍안 스테레오 이미지에서 깊이 ^[5]정보를 추출하기 위해 정렬 기술을 사용할 수 있습니다.깊이는 왼쪽 영상과 오른쪽 영상 사이의 동일한 행의 차이로 얻을 수 있습니다.인접한 행의 깊이가 비슷해야 하므로 GTW를 사용하여 추출 결과를 개선할 수 있습니다.

서명 식별

서명에는 일반적으로 x 위치, y 위치 및 ^[6]압력과 같은 여러 피쳐 시퀀스가 포함됩니다.이러한 피쳐 시퀀스는 상관 관계가 있으며, 이는 두 시그니처를 비교할 때 쌍별 정렬을 통해 얻은 거리 측도가 최적이 아님을 나타냅니다.GTW는 형상 간의 의존성을 고려하여 더 나은 거리 측정을 제공할 수 있습니다.

생물학적 배열 정렬

생물학적 시퀀스 데이터 세트에서는 시퀀스 간에 일부 구조 정보가 있는 것이 일반적입니다.LC-MS 데이터에서 근처 프로파일의 샘플은 유사한 왜곡 패턴을 갖는 경향이 있으며 GTW는 이러한 프로파일을 공동으로 정렬하도록 확장됩니다.동일한 기법을 다른 시퀀스의 조인트 정렬에도 적용할 수 있습니다.서열 사이의 구조 정보는 DNA와 아미노산 데이터에도 존재합니다.예를 들어, 관련된 종들 사이의 서열은 더 멀리 떨어진 종들의 서열과 비교했을 때 더 유사합니다.이 정보는 GTW에서 활용할 수 있습니다.

참고 항목

레퍼런스

^ ^a ^b Wang, Yizhi; Miller, David J; Poskanzer, Kira; Wang, Yue; Tian, Lin; Yu, Guoqiang (2016). "Graphical Time Warping for Joint Alignment of Multiple Curves". Advances in Neural Information Processing Systems. Curran Associates, Inc. 29.
^ ^a ^b Wu, Chiung-Ting; Wang, Yizhi; Wang, Yinxue; Ebbels, Timothy; Karaman, Ibrahim; Graça, Gonçalo; Pinto, Rui; Herrington, David M; Wang, Yue; Yu, Guoqiang (1 May 2020). "Targeted realignment of LC-MS profiles by neighbor-wise compound-specific graphical time warping with misalignment detection". Bioinformatics. 36 (9): 2862–2871. doi:10.1093/bioinformatics/btaa037. PMC 7203744. PMID 31950989.
^ ^a ^b Mi, Xuelong; Wang, Mengfan; Chen, Alex; Lim, Jing-Xuan; Wang, Yizhi; Ahrens, Misha B.; Yu, Guoqiang (6 December 2022). "BILCO: An Efficient Algorithm for Joint Alignment of Time Series". Advances in Neural Information Processing Systems. 35: 36270–36281.
^ Wang, Yizhi; DelRosso, Nicole V.; Vaidyanathan, Trisha V.; Cahill, Michelle K.; Reitman, Michael E.; Pittolo, Silvia; Mi, Xuelong; Yu, Guoqiang; Poskanzer, Kira E. (November 2019). "Accurate quantification of astrocyte and neurotransmitter fluorescence dynamics for single-cell and population-level physiology". Nature Neuroscience. 22 (11): 1936–1944. doi:10.1038/s41593-019-0492-2. ISSN 1546-1726. PMC 6858541. PMID 31570865.
^ Ishikawa, Hiroshi; Geiger, Davi (1998). "Occlusions, discontinuities, and epipolar lines in stereo". Computer Vision — ECCV'98. Lecture Notes in Computer Science. Springer. 1406: 232–248. doi:10.1007/BFb0055670. ISBN 978-3-540-64569-6.
^ Okawa, Manabu (2019). "Template Matching Using Time-Series Averaging and DTW With Dependent Warping for Online Signature Verification". IEEE Access. 7: 81010–81019. doi:10.1109/ACCESS.2019.2923093. S2CID 195774867.

[GTW-1] Wang, Yizhi; Miller, David J; Poskanzer, Kira; Wang, Yue; Tian, Lin; Yu, Guoqiang (2016). "Graphical Time Warping for Joint Alignment of Multiple Curves". Advances in Neural Information Processing Systems. Curran Associates, Inc. 29.

[ncGTW-2] Wu, Chiung-Ting; Wang, Yizhi; Wang, Yinxue; Ebbels, Timothy; Karaman, Ibrahim; Graça, Gonçalo; Pinto, Rui; Herrington, David M; Wang, Yue; Yu, Guoqiang (1 May 2020). "Targeted realignment of LC-MS profiles by neighbor-wise compound-specific graphical time warping with misalignment detection". Bioinformatics. 36 (9): 2862–2871. doi:10.1093/bioinformatics/btaa037. PMC 7203744. PMID 31950989.

[BILCO-3] Mi, Xuelong; Wang, Mengfan; Chen, Alex; Lim, Jing-Xuan; Wang, Yizhi; Ahrens, Misha B.; Yu, Guoqiang (6 December 2022). "BILCO: An Efficient Algorithm for Joint Alignment of Time Series". Advances in Neural Information Processing Systems. 35: 36270–36281.

[4] Wang, Yizhi; DelRosso, Nicole V.; Vaidyanathan, Trisha V.; Cahill, Michelle K.; Reitman, Michael E.; Pittolo, Silvia; Mi, Xuelong; Yu, Guoqiang; Poskanzer, Kira E. (November 2019). "Accurate quantification of astrocyte and neurotransmitter fluorescence dynamics for single-cell and population-level physiology". Nature Neuroscience. 22 (11): 1936–1944. doi:10.1038/s41593-019-0492-2. ISSN 1546-1726. PMC 6858541. PMID 31570865.

[5] Ishikawa, Hiroshi; Geiger, Davi (1998). "Occlusions, discontinuities, and epipolar lines in stereo". Computer Vision — ECCV'98. Lecture Notes in Computer Science. Springer. 1406: 232–248. doi:10.1007/BFb0055670. ISBN 978-3-540-64569-6.

[6] Okawa, Manabu (2019). "Template Matching Using Time-Series Averaging and DTW With Dependent Warping for Online Signature Verification". IEEE Access. 7: 81010–81019. doi:10.1109/ACCESS.2019.2923093. S2CID 195774867.

[1]

[2]

[3]

[4]

[5]

[6]

Search