Constantes de Chvátal-Sankoff

Concepto de matemáticas

En matemáticas , las constantes de Chvátal-Sankoff son constantes matemáticas que describen las longitudes de las subsecuencias comunes más largas de cadenas aleatorias . Aunque se ha demostrado la existencia de estas constantes, se desconocen sus valores exactos. Llevan el nombre de Václav Chvátal y David Sankoff , quienes comenzaron a investigarlos a mediados de los años 1970. ^{[1] [2]}

Hay una constante de Chvátal-Sankoff para cada entero positivo k , donde k es el número de caracteres del alfabeto de los que se extraen las cadenas aleatorias. La secuencia de estos números crece inversamente proporcional a la raíz cuadrada de k . ^[3] Sin embargo, algunos autores escriben "la constante de Chvátal-Sankoff" para referirse a , la constante definida de esta manera para el alfabeto binario. ^[4] ${\displaystyle \gamma _{k}}$ ${\displaystyle \gamma _{2}}$

Fondo

Una subsecuencia común de dos cadenas S y T es una cadena cuyos caracteres aparecen en el mismo orden (no necesariamente consecutivamente) tanto en S como en T. El problema de calcular una subsecuencia común más larga ha sido bien estudiado en informática. Puede resolverse en tiempo polinomial mediante programación dinámica ; ^[5] este algoritmo básico tiene aceleraciones adicionales para alfabetos pequeños (el Método de los Cuatro Rusos ), ^[6] para cadenas con pocas diferencias, ^[7] para cadenas con pocos pares de caracteres coincidentes, ^[8] etc. Este problema y sus Las generalizaciones a formas más complejas de edición a distancia tienen aplicaciones importantes en áreas que incluyen bioinformática (en la comparación de secuencias de ADN y proteínas y la reconstrucción de árboles evolutivos ), geología (en estratigrafía ) e informática (en comparación de datos y control de revisión ). . ^[7]

Una motivación para estudiar las subsecuencias comunes más largas de cadenas aleatorias, ya dada por Chvátal y Sankoff, es calibrar los cálculos de las subsecuencias comunes más largas en cadenas que no son aleatorias. Si dicho cálculo arroja una subsecuencia que es significativamente más larga que la que se obtendría al azar, se podría inferir de este resultado que la coincidencia es significativa. ^[1]

Definición y existencia

Las constantes de Chvátal-Sankoff describen el comportamiento del siguiente proceso aleatorio. Dados los parámetros n y k , elija dos cadenas S y T de longitud n del mismo alfabeto de k símbolos, con cada carácter de cada cadena elegido uniformemente al azar , independientemente de todos los demás caracteres. Calcule una subsecuencia común más larga de estas dos cadenas y sea la variable aleatoria cuyo valor es la longitud de esta subsecuencia. Entonces el valor esperado de es (hasta términos de orden inferior) proporcional a  n , y la k -ésima constante de Chvátal-Sankoff es la constante de proporcionalidad . ^[2] ${\displaystyle \lambda _{n,k}}$ ${\displaystyle \lambda _{n,k}}$ ${\displaystyle \gamma _{k}}$

Más precisamente , el valor esperado es superaditivo : para todo m y n ,. Esto se debe a que, si cadenas de longitud m  +  n se dividen en subcadenas de longitudes m y n , y se encuentran las subsecuencias comunes más largas de esas subcadenas, se pueden concatenar juntas para obtener una subcadena común de todas las cadenas. De un lema de Michael Fekete ^[9] se desprende que el límite ${\displaystyle \operatorname {E} [\lambda _{n,k}]}$ ${\displaystyle \operatorname {E} [\lambda _{m+n,k}]\geq \operatorname {E} [\lambda _{m,k}]+\operatorname {E} [\lambda _{n,k}]}$

${\displaystyle \gamma _{k}=\lim _{n\to \infty }{\frac {\operatorname {E} [\lambda _{n,k}]}{n}}}$

existe y es igual al supremo de los valores . Estos valores límite son las constantes de Chvátal-Sankoff. ^[2] ${\displaystyle \operatorname {E} [\lambda _{n,k}]/n}$ ${\displaystyle \gamma _{k}}$

Límites

Los valores exactos de las constantes de Chvátal-Sankoff siguen siendo desconocidos, pero se han demostrado límites superiores e inferiores rigurosos.

Debido a que es un supremo de los valores , cada uno de los cuales depende sólo de una distribución de probabilidad finita, una forma de demostrar límites inferiores rigurosos sería calcular los valores exactos de ; sin embargo, este método escala exponencialmente en n , por lo que solo se puede implementar para valores pequeños de n , lo que genera un límite inferior débil. En su doctorado. tesis, Vlado Dančík fue pionero en un enfoque alternativo en el que se utiliza un autómata finito determinista para leer símbolos de dos cadenas de entrada y producir una subsecuencia común (larga pero no óptima) de estas entradas. El comportamiento de este autómata ante entradas aleatorias se puede analizar como una cadena de Markov , cuyo estado estacionario determina la velocidad a la que encuentra elementos de la subsecuencia común para valores grandes de n . Esta tasa es necesariamente un límite inferior de la constante de Chvátal-Sankoff. ^[10] Utilizando el método de Dančík, con un autómata cuyo espacio de estado almacena en buffer los caracteres h más recientes de sus dos cadenas de entrada, y con técnicas adicionales para evitar el costoso análisis de cadena de Markov en estado estacionario de este enfoque, Lueker (2009) pudo para realizar un análisis computarizado con n  = 15 que resultó . ${\displaystyle \gamma _{k}}$ ${\displaystyle \operatorname {E} [\lambda _{n,k}]}$ ${\displaystyle \gamma _{k}}$ ${\displaystyle \operatorname {E} [\lambda _{n,k}]}$ ${\displaystyle \gamma _{2}\geq 0.788071}$

Se pueden generalizar métodos similares a alfabetos no binarios. Los límites inferiores obtenidos de esta manera para varios valores de k son: ^[4]

Dančík y Paterson (1995) también utilizaron métodos teóricos de autómatas para demostrar los límites superiores de las constantes de Chvátal-Sankoff, y nuevamente Lueker (2009) amplió estos resultados mediante cálculos computarizados. El límite superior que obtuvo fue . Este resultado refutó una conjetura de J. Michael Steele de que , porque este valor es mayor que el límite superior. ^[11] La evidencia numérica no rigurosa sugiere que está aproximadamente más cerca del límite superior que del límite inferior. ^[12] ${\displaystyle \gamma _{2}\leq 0.826280}$ ${\displaystyle \gamma _{2}=2/(1+{\sqrt {2}})}$ ${\displaystyle \gamma _{2}}$ ${\displaystyle 0.811}$

En el límite cuando k llega al infinito, las constantes crecen de manera inversamente proporcional a la raíz cuadrada de k . Más precisamente, ^[3] ${\displaystyle \gamma _{k}}$

${\displaystyle \lim _{k\to \infty }\gamma _{k}{\sqrt {k}}=2.}$

Distribución de longitudes de LCS.

También se han investigado la distribución de valores de la subsecuencia común más larga, generalizando el estudio de la expectativa de este valor. Por ejemplo, se sabe que la desviación estándar de la longitud de la subsecuencia común más larga de cadenas aleatorias de longitud n es proporcional a la raíz cuadrada de  n . ^[13]

Una complicación al realizar este tipo de análisis es que las variables aleatorias que describen si los caracteres en diferentes pares de posiciones coinciden entre sí no son independientes entre sí. Para una simplificación más manejable matemáticamente del problema de subsecuencia común más larga, en el que las coincidencias permitidas entre pares de símbolos no están controladas por si esos símbolos son iguales entre sí sino por variables aleatorias independientes con probabilidad 1/ k de ser 1 y ( k  − 1)/ k de ser 0, se ha demostrado que la distribución de la longitud de subsecuencia común más larga está controlada por la distribución de Tracy-Widom . ^[14]

Referencias

1. Chvatal, Václáv ; Sankoff, David (1975), "Subsecuencias comunes más largas de dos secuencias aleatorias", Journal of Applied Probability , 12 (2): 306–315, doi :10.2307/3212444, JSTOR  3212444, MR  0405531, S2CID  250345191.
2. Finch, Steven R. (2003), "5.20.2 Subsecuencias comunes", Constantes matemáticas, Enciclopedia de las matemáticas y sus aplicaciones, Cambridge University Press, págs. 384–385, ISBN 9780521818056.
3. Kiwi, Marcos; Loebl, Martín; Matoušek, Jiří (2005), "Longitud esperada de la subsecuencia común más larga para alfabetos grandes", Avances en Matemáticas , 197 (2): 480–498, arXiv : math/0308234 , doi : 10.1016/j.aim.2004.10.012 , señor  2173842.
4. Kiwi, M.; Soto, J. (2009), "Sobre una relación especulada entre las constantes de Chvátal-Sankoff de varias secuencias", Combinatoria, probabilidad y computación , 18 (4): 517–532, arXiv : 0810.1066 , doi : 10.1017/S0963548309009900, MR  2507735 , S2CID  10882010.
5. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "15.4", Introducción a los algoritmos (2ª ed.), MIT Press y McGraw-Hill, págs. 350–355, ISBN 0-262-53196-8.
6. Masek, William J.; Paterson, Michael S. (1980), "Un algoritmo más rápido que calcula distancias de edición de cadenas", Journal of Computer and System Sciences , 20 (1): 18–31, doi : 10.1016/0022-0000(80)90002-1 , SEÑOR  0566639.
7. Sankoff, David ; Kruskal, Joseph B. (1983), Deformaciones del tiempo, ediciones de cadenas y macromoléculas: la teoría y práctica de la comparación de secuencias , Addison-Wesley, Bibcode : 1983twse.book.....S.
8. Caza, James W.; Szymanski, Thomas G. (1977), "Un algoritmo rápido para calcular las subsecuencias comunes más largas", Communications of the ACM , 20 (5): 350–353, doi : 10.1145/359581.359603 , MR  0436655, S2CID  3226080.
9. Fekete, M. (1923), "Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten", Mathematische Zeitschrift (en alemán), 17 (1): 228–249, doi :10.1007/BF01504345, S2CID  186223729.
10. Dančík, Vlado; Paterson, Mike (1995), "Límites superiores para la longitud esperada de una subsecuencia común más larga de dos secuencias binarias", Estructuras y algoritmos aleatorios , 6 (4): 449–458, doi :10.1002/rsa.3240060408, MR  1368846.
11. Lueker, George S. (2009), "Límites mejorados en la longitud promedio de las subsecuencias comunes más largas", Journal of the ACM , 56 (3), A17, doi :10.1145/1516512.1516519, MR  2536132, S2CID  7232681.
12. Dixon, John D. (2013), Subsecuencias comunes más largas en secuencias binarias , arXiv : 1307.2796 , Bibcode :2013arXiv1307.2796D.
13. Lember, Jüri; Matzinger, Heinrich (2009), "Desviación estándar de la subsecuencia común más larga", The Annals of Probability , 37 (3): 1192–1235, arXiv : 0907.5137 , doi : 10.1214/08-AOP436, MR  2537552, S2CID  8143348.
14. Majumdar, Satya N.; Nechaev, Sergei (2005), "Resultados asintóticos exactos para el modelo de coincidencia de alineación de secuencias de Bernoulli", Physical Review E , 72 (2): 020901, 4, arXiv : q-bio/0410012 , Bibcode : 2005PhRvE..72b0901M, doi :10.1103/PhysRevE.72.020901, SEÑOR  2177365, PMID  16196539, S2CID  11390762.