Una coincidencia única máxima o MUM , por sus siglas en inglés, es parte de un paso clave [1] en la alineación de secuencias múltiples de genomas en biología computacional . La identificación de MUM y otros anclajes potenciales es el primer paso en sistemas de alineación más grandes como MUMmer . Los anclajes son las áreas entre dos genomas donde son altamente similares. Para entender qué es una MUM, cada palabra en el acrónimo se puede desglosar individualmente. Coincidencia implica que la subcadena ocurre en ambas secuencias que se van a alinear. Única significa que la subcadena ocurre solo una vez en cada secuencia. Finalmente, máxima indica que la subcadena no es parte de otra cadena más grande que cumpla con ambos requisitos anteriores. La idea detrás de esto es que las secuencias largas que coinciden exactamente y ocurren solo una vez en cada genoma son casi con certeza parte de la alineación global.
"Dados dos genomas A y B, la subcadena de coincidencia única máxima (MUM) es una subcadena común de A y B de longitud mayor que una longitud mínima especificada d (por defecto d = 20) tal que
- es máxima, es decir, no se puede extender en ninguno de los extremos sin incurrir en un desajuste y
- "Es único en ambas secuencias" [2]
Identificar el conjunto de MUM en dos secuencias de genoma muy largas no es computacionalmente trivial. [1] Hay varias formas algorítmicas de abordar la identificación de MUM en alineamiento de secuencias múltiples. El método más simple y lento es usar fuerza bruta donde para cada índice i en el genoma A y cada índice j en el genoma B , se calcula el prefijo común más largo (P) de A[i...n] y B[j...m] . A continuación, debe garantizar que la longitud de P sea al menos d donde d es el tamaño mínimo de MUM especificado. Finalmente, debe asegurarse de que P sea único en ambos genomas. La complejidad del método de fuerza bruta es, por lo tanto, O(mn) . [2]
En realidad, los MUM se identifican mediante la construcción de un árbol de sufijos generalizado para A y B. Luego se crea una lista para todos los nodos internos con exactamente un hijo de cada secuencia del genoma. Para cada uno de estos nodos (identificaremos a los hijos del genoma A como i y a los hijos del genoma B como j ), se comprueba que A[i-1] ≠ B[j-1] y, para aquellos en los que se cumple esta condición, sabemos que se trata de un MUM. En este caso, la complejidad se reduce a O(m+n) . [2]
En la siguiente ilustración, dadas las cadenas iniciales S y T y un d de 1, las MUM deberían ser G y TA. Una hoja roja denota que la hoja proviene de la cadena S y una hoja azul denota la cadena T. El nodo interno en A fue descartado porque A[i-1] = B[j-1], lo que significa que el carácter que viene antes de ambas A es idéntico (T), esta es una condición en la que las secuencias pertenecen a una secuencia única más grande. El nodo interno en C se descarta porque tiene dos hijos de S. Esto nos deja con las MUM de G y TA.
Para ilustrar mejor los MUM, tomemos el siguiente ejemplo. Supongamos que d=3 y nuestros dos genomas son los siguientes:
S = CTACTGTCATGCTGAAGTCATGCGGCTGGCTTAT#
T = CTGGTGTGATGCTAAGTCATGCGGTCTGGCTTAT$
Trabajando a través de la secuencia nuestro primer MUM que satisface las condiciones ocurre aquí:
S = CTAC TGT CATGCTGAAGTCATGCGGCTGGCTTAT#
T = CTGG TGT GATGCTAAGTCATGCGGTCTGGCTTAT$
TGT tiene una longitud de al menos d, aparece solo una vez en ambas secuencias y los caracteres de la izquierda y la derecha difieren entre genomas. Para ilustrar un ejemplo en el que se necesita expansión para garantizar que nuestro MUM no sea parte de una secuencia más grande y única, tomemos lo siguiente:
S = CTAC TGT C ATG CTGAAGTCATGCGGCTGGCTTAT#
T = CTGG TGT G ATG CTAAGTCATGCGGTCTGGCTTAT$
Hay dos problemas en el caso de probar ATG como MUM porque ATG no es único y también es parte de una subsecuencia más grande como se ilustra aquí:
S = CTAC TGT C ATG CTGAAGTC ATGC GGCTGGCTTAT#
T = CTGG TGT G ATG CTAAGTC ATGC GGTCTGGCTTAT$
Por lo tanto, se requiere la expansión de esta secuencia en un intento de satisfacer las condiciones para ser un MUM como se muestra aquí.
S = CTAC TGT C ATGCT GAAGTC ATGCG GCTGGCTTAT#
T = CTGG TGT G ATGCT AAGTC ATGCG GTCTGGCTTAT$
Al utilizar este método se produce de forma iterativa un producto final en el que cada MUM se identifica para mayor claridad y cada MUM está codificado por color:
S = CTAC TGT C ATGCT G AAGTCATGCGG CTGGCTTAT #
T = ACTT TGT G ATGCT AAGTCATGCGG T CTGGCTTAT $
Los MUM son un subconjunto de un conjunto más grande denominado Coincidencias Máximas Exactas o MEMS. En un MEM, la condición de unicidad de los MUM es relajada. Los MEM son como la alineación local , pero en este caso solo identifican secuencias donde no hay espacios vacíos.