Distorsión temporal gráfica

Supongamos que hay${\displaystyle N}$pares de series temporales${\displaystyle \{(x_{n},y_{n})|n=1,2,...,N\}}$y cada par${\displaystyle {x_{n},y_{n}}}$tiene una trayectoria de deformación correspondiente${\displaystyle P_{n}}$. Se sabe que algunos pares de trayectorias de deformación son similares, y el conjunto de todos esos pares se denota como${\displaystyle {(m,n)}}$. Por ejemplo, si${\displaystyle (m,n)}$está en este conjunto, caminos deformados${\displaystyle P_{m}}$y${\displaystyle P_{n}}$son similares. Para optimizar tanto la similitud entre las series temporales alineadas como las distancias de las trayectorias de deformación, el problema de alineación conjunta se formula como un problema de minimización:

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

Aquí${\displaystyle costo(P_{n})}$denota la distancia entre${\displaystyle x_{n}}$y${\displaystyle y_{n}}$después de la alineación con la función de deformación${\displaystyle P_{n}}$,${\displaystyle dist(P_{m},P_{n})}$es la distancia entre trayectorias de deformación${\displaystyle P_{m}}$y${\displaystyle P_{n}}$definido por el área de la región delimitada por${\displaystyle P_{m}}$y${\displaystyle P_{n}}$, y${\displaystyle \kappa }$es un hiperparámetro que equilibra el término de costo de alineación de la serie temporal y el término de distancia de la función de deformación.

Tenga en cuenta que la fuerza de similitud puede ser específica de la aplicación o diseñada por el usuario. Para diferentes pares de rutas de deformación relacionadas${\displaystyle (m,n)}$Podemos establecer diferentes parámetros${\displaystyle \kappa _{(}m,n)}$. Para simplificar, aquí utilizamos el hiperparámetro unificado${\displaystyle \kappa }$.

El problema de minimización anterior se formula de forma intuitiva. Sin embargo, no está claro cómo resolverlo eficientemente en su forma original, y una enumeración ingenua de las trayectorias de deformación conduce a un problema NP-difícil .

Este problema de minimización puede reformularse como un problema de corte mínimo en un grafo especial denominado grafo GTW, donde el corte mínimo y las trayectorias de deformación son equivalentes. ^{[ 1 ]} La formulación podría describirse como:

• Para el${\displaystyle n_{t}h}$Para cada par de series temporales, construya su grafo DTW. Luego, convierta este grafo DTW en su grafo dual , denominado subgrafo GTW.${\displaystyle G^{n}}$. Establezca las capacidades de las aristas inversas como infinitas.
• Para cada par de trayectorias de deformación similares${\displaystyle P_{m}}$y${\displaystyle P_{n}}$, uniendo los nodos de la misma posición en${\displaystyle G^{m}}$y${\displaystyle G^{n}}$mediante aristas bidireccionales con capacidad${\displaystyle \kappa /2}$Estos bordes se denominan bordes transversales.
• El gráfico GTW construido, como se muestra en la figura, consta de:${\displaystyle N}$Subgrafos GTW y aristas transversales.
• Utilizando algoritmos de flujo máximo para obtener el corte mínimo del grafo construido. El corte mínimo dentro de cada subgrafo GTW corresponde a una ruta de deformación.

Cada subgrafo GTW${\displaystyle G^{n}}$es el grafo dual del grafo DTW que representa la alineación de un único par de series temporales. Como resultado, el corte dentro de un subgrafo GTW es dual a una ruta de deformación en el grafo DTW, y el término de costo de alineación de perfil puede representarse mediante el costo de corte dentro de los subgrafos. Las capacidades infinitas de las aristas inversas se utilizan para garantizar la monotonicidad y la continuidad de las rutas de deformación.

Los bordes transversales restringen la similitud de las trayectorias de deformación y contribuyen al término de distancia en la función objetivo. Nótese que en un problema de corte mínimo , los nodos eventualmente se asignarían al lado de origen o al lado de destino, y el corte final está definido por los bordes entre dos lados. Cada par de nodos no coincidentes en${\displaystyle G^{m}}$y${\displaystyle G^{n}}$contribuir a la distancia entre${\displaystyle P_{m}}$y${\displaystyle P_{n}}$y resultaría en un extra${\displaystyle \kappa /2}$costo. Por lo tanto, el término de distancia podría representarse mediante el costo de corte en los bordes transversales.

Por lo tanto, el costo de corte en el grafo GTW corresponde a los términos de costo en la función objetivo . Recordando que el corte dentro de cada subgrafo corresponde a la trayectoria de deformación de un par de series temporales, el corte mínimo del grafo GTW corresponde a la solución óptima de trayectorias de deformación en la alineación conjunta.

En el alineamiento de secuencias múltiples , el objetivo es alinear todas las secuencias a una referencia común. Sin embargo, esta referencia común suele ser desconocida. Además, existe información estructural entre las secuencias. Si bien GTW no se puede aplicar directamente en estas aplicaciones, se desarrolló un marco de dos etapas llamado ncGTW sobre GTW para resolver este problema. En la primera etapa, se utiliza el conocimiento estructural previo entre las secuencias para obtener las funciones de deformación. En la segunda etapa, estas funciones de deformación ayudan a alinear conjuntamente todas las secuencias a una referencia virtual, que no necesita especificarse explícitamente. ncGTW se aplicó a problemas de alineamiento de perfiles LC-MS en datos de proteómica y obtuvo mejores resultados que los enfoques existentes. ^{[ 2 ]}

Resolver el problema del corte mínimo en el grafo GTW mediante algoritmos tradicionales de flujo máximo requeriría un tiempo de ejecución prolongado y un alto consumo de memoria debido al gran tamaño del grafo, lo que limita el uso de GTW. El algoritmo BILCO utiliza dos propiedades importantes del problema de alineación conjunta y logra una mejora promedio de 10 veces tanto en el tiempo de ejecución como en el consumo de memoria. Las dos propiedades son:

• El problema de alineación conjunta es una generalización de la alineación por pares, y existen numerosos problemas DTW integrados en el grafo GTW. Dado que cada subgrafo GTW es dual a un grafo DTW, el flujo máximo dentro de cada subgrafo GTW se puede resolver en tiempo lineal mediante programación dinámica .
• En muchas aplicaciones, se puede estimar una solución aproximada de las trayectorias de deformación, que podría servir como punto de partida para acelerar el proceso de resolución.

Según la primera propiedad, BILCO divide el intercambio de flujo en dos tipos: (1) Intercambio de flujo dentro del subgrafo GTW; (2) Intercambio de flujo entre subgrafos GTW relacionados. El proceso puede compararse con el bombeo de agua desde depósitos conectados, y los dos tipos de intercambio de flujo se denominan Drenaje y Descarga . Para aprovechar al máximo esta propiedad, se utilizan componentes (cada componente es un subconjunto conectado del subgrafo GTW), en lugar de nodos individuales, como unidad de operación. Ambas operaciones de componentes , Drenaje y Descarga, pueden implementarse en tiempo lineal.

La segunda propiedad inspira la estrategia de empuje bidireccional. En esta estrategia, BILCO primero segmenta el grafo en dos partes utilizando la solución aproximada inicial, y luego empuja el exceso/déficit en las partes de sumidero/fuente obtenidas, respectivamente. En comparación con los algoritmos de flujo máximo basados ​​en empuje y reetiquetado existentes, BILCO reduce significativamente el cálculo redundante. Cabe destacar que dicha estrategia también podría utilizarse para ayudar a acelerar otros algoritmos basados ​​en empuje y reetiquetado . ^{[ 3 ]}

En los datos de bioimágenes de lapso de tiempo, la propagación de la señal es un fenómeno ampliamente observado en muchos tipos de células. ^{[ 4 ]} El estudio de la propagación de la señal puede ayudar a descubrir la función de estas células tanto en condiciones normales como patológicas. La información de propagación podría derivarse de las trayectorias de deformación alineando las curvas de los píxeles con una señal de referencia. Debido a la baja relación señal-ruido en los datos de bioimágenes, los métodos de alineación por pares suelen dar resultados insatisfactorios. Considerando la correlación espacial de las señales, la similitud de las trayectorias de deformación entre píxeles adyacentes puede utilizarse en GTW para mejorar el rendimiento de la alineación, lo que puede conducir a un cálculo más preciso de las propiedades de propagación.

En imágenes estéreo binoculares , se puede utilizar una técnica de alineación para extraer información de profundidad. ^{[ 5 ]} La profundidad se puede obtener a partir de la disparidad de la misma fila entre la imagen izquierda y la derecha. Dado que la profundidad de las filas adyacentes debe ser similar, se puede utilizar GTW para mejorar el resultado de la extracción.

Una firma generalmente contiene múltiples secuencias de características, como la posición x, la posición y y la presión. ^{[ 6 ]} Estas secuencias de características están correlacionadas, lo que indica que al comparar dos firmas, la medida de distancia obtenida mediante alineación por pares no es óptima. GTW podría tener en cuenta la dependencia entre las características y proporcionar una mejor medida de distancia.

En un conjunto de datos de secuencias biológicas , es común encontrar información estructural entre las secuencias. En los datos de LC-MS, las muestras de perfiles cercanos tienden a presentar patrones de distorsión similares , y GTW se extiende para alinear conjuntamente estos perfiles. Esta misma técnica también puede aplicarse a la alineación conjunta de otras secuencias. La información estructural entre secuencias también está presente en los datos de ADN y aminoácidos. Por ejemplo, las secuencias entre especies emparentadas son más similares que las secuencias de especies menos emparentadas. GTW podría aprovechar esta información.