Alineación de los árboles

En bioinformática , el método básico de procesamiento de información consiste en contrastar los datos de secuencias. Los biólogos lo utilizan para descubrir la función, la estructura y la información evolutiva en las secuencias biológicas. Los siguientes análisis se basan en el ensamblaje de secuencias : el análisis filogenético , la comparación de haplotipos y la predicción de la estructura del ARN . Por lo tanto, la eficiencia del alineamiento de secuencias influye directamente en la eficacia para resolver estos problemas. Para diseñar un alineamiento de secuencias racional y eficiente, la derivación de algoritmos se ha convertido en una rama importante de la investigación en el campo de la bioinformática.

En general, el alineamiento de secuencias consiste en construir una cadena a partir de dos o más cadenas dadas con la mayor similitud posible, añadiendo o eliminando letras, o agregando un espacio a cada una . El problema del alineamiento múltiple de secuencias se basa generalmente en el alineamiento de secuencias por pares y, actualmente, para este problema, los biólogos pueden utilizar un enfoque de programación dinámica para obtener su solución óptima. Sin embargo, el problema del alineamiento múltiple de secuencias sigue siendo uno de los más complejos en bioinformática. Esto se debe a que encontrar la solución óptima para el alineamiento múltiple de secuencias ha demostrado ser un problema NP-completo y solo se puede obtener una solución óptima aproximada. ^{[ 2 ]}

El método de distancia mide el número mínimo de operaciones de inserciones , eliminaciones y sustituciones de caracteres que se requieren para transformar una secuencia u en otra secuencia v cuando se opera sobre un par de cadenas. El cálculo de la distancia de edición puede basarse en programación dinámica , y la ecuación es en tiempo O(|u|×|v|), donde |u| y |v| son las longitudes de u y v. ^{[ 3 ]} La estimación eficiente de la distancia de edición es esencial ya que el método de distancia es un principio básico en biología computacional ^{[ 4 ]} Para funciones de propiedades hereditarias se puede utilizar la "simetrización". Debido a que se utiliza una serie de funciones para calcular la distancia de edición, diferentes funciones pueden dar resultados diferentes. Encontrar una función de distancia de edición óptima es esencial para el problema de alineación de árboles.

Cuando se utiliza la estrategia de optimización combinatoria para transformar el alineamiento de secuencias múltiples en alineamiento de secuencias por pares, el problema principal cambia de "Cómo mejorar la eficiencia del alineamiento de secuencias múltiples" a "Cómo mejorar la eficiencia del alineamiento de secuencias por pares". La teoría del árbol de palabras clave y el algoritmo de búsqueda de Aho-Corasick constituyen un enfoque eficiente para resolver el problema del alineamiento de secuencias por pares. El objetivo de combinar la teoría del árbol de palabras clave y el algoritmo de búsqueda de Aho-Corasick es resolver este tipo de problema: para una cadena larga dada${\displaystyle T}$y un conjunto de cuerdas cortas${\displaystyle P}$={${\displaystyle p_{1}}$,${\displaystyle p_{2}}$,... ,${\displaystyle p_{z}}$} (z∈N,z>1), encuentra la ubicación de todos${\displaystyle P_{i}}$en${\displaystyle T}$. El árbol de palabras clave producido por el conjunto${\displaystyle P}$se utiliza y luego se busca en${\displaystyle T}$con este árbol de palabras clave a través del algoritmo de búsqueda de Aho-Corasick. ^{[ 6 ]} La complejidad temporal total de usar este método para encontrar todos${\displaystyle P_{i}}$La ubicación de en T es O(${\displaystyle m}$+${\displaystyle n}$+${\displaystyle k}$), dónde${\displaystyle m}$=|${\displaystyle T}$| (la longitud de${\displaystyle T}$),${\displaystyle n}$=Σ|${\displaystyle P_{i}}$| (la suma de todos${\displaystyle P_{i}}$longitudes) y${\displaystyle k}$significa la suma de ocurrencias para todos${\displaystyle P_{i}}$en${\displaystyle T}$.

Generalmente, los algoritmos heurísticos se basan en la estrategia iterativa , es decir, a partir de un método de comparación, optimizan los resultados del alineamiento de secuencias múltiples mediante un proceso iterativo. Davie M. propuso utilizar el algoritmo de optimización por enjambre de partículas para resolver el problema del alineamiento de secuencias múltiples; Ikeda Takahiro propuso un algoritmo heurístico basado en el algoritmo de búsqueda A* ; E. Birney propuso por primera vez utilizar el modelo oculto de Markov para resolver el problema del alineamiento de secuencias múltiples; y muchos otros biólogos utilizan el algoritmo genético para resolverlo. ^{[ 8 ] [ 9 ]} Todos estos algoritmos son generalmente robustos e insensibles al número de secuencias, pero también tienen deficiencias. Por ejemplo, los resultados del algoritmo de optimización por enjambre de partículas son inestables y sus méritos dependen de la selección de números aleatorios, el tiempo de ejecución del algoritmo de búsqueda A* es demasiado largo, y el algoritmo genético es fácil que caiga en un estado de excelencia local.

En términos generales, el grafo de alineación de árboles tiene como objetivo alinear árboles en un grafo y, finalmente, sintetizarlos para desarrollar estadísticas. En biología, los grafos de alineación de árboles (TAG) se utilizan para eliminar los conflictos evolutivos o los taxones superpuestos de conjuntos de árboles y luego se pueden consultar para explorar la incertidumbre y el conflicto. Al integrar métodos de alineación, síntesis y análisis, el TAG busca resolver las relaciones conflictivas y los conjuntos de taxones parcialmente superpuestos obtenidos de una amplia gama de secuencias. Además, el grafo de alineación de árboles sirve como un enfoque fundamental para ejercicios de superárboles e injertos , que Berry ha probado con éxito para construir superárboles. ^{[ 10 ]} Debido a que la transformación de árboles a un grafo contiene nodos y aristas similares de sus árboles de origen, los TAG también pueden proporcionar la extracción de los árboles de origen originales para un análisis posterior. Un TAG es una combinación de un conjunto de árboles alineados. Puede almacenar hipótesis conflictivas de relaciones evolutivas y sintetizar los árboles de origen para desarrollar hipótesis evolutivas. Por lo tanto, es un método básico para resolver otros problemas de alineación. ^{[ 11 ]}