MUMmer - MUMmer
MUMmer es un sistema de software bioinformático para la alineación de secuencias . Se basa en la estructura de datos de árbol de sufijos y es uno de los sistemas más rápidos y eficientes disponibles para esta tarea, lo que permite su aplicación a secuencias muy largas. Se ha utilizado ampliamente para comparar diferentes genomas entre sí. En los últimos años se ha convertido en un algoritmo popular para comparar conjuntos de genomas entre sí, lo que permite a los científicos determinar cómo ha cambiado un genoma después de agregar más secuencias de ADN o después de ejecutar un programa de ensamblaje de genoma diferente. El acrónimo "MUMmer" proviene de "Maximal Unique Matches" o MUM. Los algoritmos originales del paquete de software MUMMER fueron diseñados por Art Delcher, Simon Kasif y Steven Salzberg. Mummer fue el primer sistema completo de comparación del genoma desarrollado en Bioinformática. Originalmente se aplicó para comparar dos cepas de bacterias relacionadas.
El software MUMmer es de código abierto y se puede encontrar en la página de inicio de MUMmer. La página de inicio también tiene enlaces a documentos técnicos que describen el sistema. El sistema es mantenido principalmente por Steven Salzberg y Arthur Delcher en el Centro de Biología Computacional de la Universidad Johns Hopkins .
MUMmer es un sistema bioinformático muy citado en la literatura científica. Según Google Scholar, a principios de 2013, el artículo original de MUMmer (Delcher et al., 1999) ha sido citado 691 veces; el artículo de MUMmer 2 (Delcher et al., 2002) ha sido citado 455 veces; y el artículo de MUMmer 3.0 (Kurtz et al., 2004) ha sido citado 903 veces.
Descripción general
¿Qué es MUMmer?
¿Te has preguntado cómo estás relacionado con un mono? Si la respuesta es sí, puedo decirte que existen algoritmos en los que puedes encontrar esa respuesta. Si tuviera clases de algoritmos, le vendría a la mente “Editar distancia” (de Wunch y Needleman); que se puede utilizar para este mismo tema. Sin embargo, el algoritmo de "Editar distancia" se utiliza para comparar secuencias pequeñas, tomaría mucho tiempo calcular las alineaciones del genoma.
Los genomas son una gran secuencia de instrucciones / información genética sobre un organismo (en un cromosoma); ahora, imagine “comparando una secuencia de 4 Mb como M. Tuberculosis con otra secuencia de 4 Mb, muchos algoritmos se quedan sin memoria o tardan demasiado en completarse” (Arthur et al., 1999). En aquel entonces, 4 Mb de memoria eran un gran problema; así que tenían que hacer algo al respecto, como crear este tipo de algoritmos. Los investigadores han estado creando algoritmos para comparar las secuencias del genoma. Mummer es un algoritmo rápido que se utiliza principalmente para la alineación rápida de genomas completos.
MUMmer, como se mencionó anteriormente, es el sistema / proceso para la alineación eficiente de secuencias de gran tamaño, este algoritmo se ha utilizado para hacer descubrimientos sobre la estructura del genoma. El algoritmo está muy bien diseñado y es capaz de comparar alineaciones en segundos. Dado que este algoritmo es relativamente nuevo, este algoritmo tiene cuatro versiones, una mejor que la anterior.
Versiones de MUMmers
MUMmer1
MUMmer1 o simplemente MUMmer consta de tres partes, la primera parte consiste en la creación de árboles de sufijos (para obtener MUM), la segunda parte en la subsecuencia creciente más larga o las subsecuencias comunes más largas (para ordenar MUM), por último, cualquier alineación para cerrar espacios.
Para comenzar el proceso, como recordatorio, necesitamos obtener dos genomas como entrada. Una vez que los recibamos, buscaremos las coincidencias únicas máximas ( MUM ). El algoritmo de MUM tiene su propia lógica, ya que se puede hacer de varias formas. Por ejemplo, el algoritmo ingenuo pasa por todas las secuencias de un genoma y lo compara con las otras secuencias, lo que toma O (m * m2) donde my m2 son los dos genomas. Sin embargo, dado que MUMmer tiene que ser rápido, utiliza la estructura de datos llamada árbol de sufijos ( árbol de sufijos ) que toma O (m + m2). De este árbol, extraemos los MUM (que son las subsecuencias que están representadas por un nodo interno por ambas secuencias).
Una vez que identificamos los MUM, debemos elegir un genoma y clasificar (y posiblemente eliminar) los MUM en función de la posición del otro genoma. Este paso se puede realizar fácilmente eligiendo un genoma y enumerando los nodos (MUMs) en orden ascendente, y en el otro enumeramos cada nodo según el nodo de la primera secuencia. En otras palabras, enumeramos un par de MUM (con la coincidencia exacta de ambos genomas) con el mismo valor independientemente de la posición. Luego clasificamos. Para que esto suceda, podemos elegir cualquiera de los métodos disponibles. Por ejemplo, esto se puede hacer con Subsecuencia común larga ( problema de subsecuencia común más larga ) o Subsecuencia creciente larga ( LIS ). Al final de este proceso, los MUM en ambas secuencias se alinean / ordenan por igual (algunos MUM se ignoran por ahora, ya que no podemos tener un valor enumerado con un número grande antes que uno enumerado con un número pequeño). La mejor complejidad de tiempo para este paso es O (nlogn).
Finalmente, tenemos que lidiar con la interrupción entre la alineación de MUM, que puede conocerse como brechas. Empleamos otros algoritmos de alineación que pueden llenar estos vacíos. Arthur y su equipo (Arthur et al., 1999), mencionan que las brechas caen en las siguientes cuatro clases:
- Una interrupción de SNP : al comparar dos secuencias, un carácter será diferente. En otras palabras, los caracteres antes y después de ese carácter serán iguales.
- Una inserción: al comparar dos secuencias, hay una subsecuencia en la que solo aparece en una de las secuencias. Sería un hueco vacío en la otra secuencia en el momento de comparar las dos secuencias.
- Una región altamente polimórfica: al comparar dos secuencias, se puede encontrar una subsecuencia en la que cada carácter es diferente.
- Una repetición: es la repetición de una secuencia. Dado que los MUM solo pueden tomar secuencias únicas, ese espacio puede ser una repetición de uno de los MUM.
MUMmer 2
Este algoritmo fue rediseñado para requerir menos memoria, el proceso se ejecuta más rápido y es más preciso que el primero; También permite una mayor alineación de genomas.
La mejora fue la cantidad almacenada en los árboles de sufijos al emplear el creado por Kurtz. Para este árbol, la inserción es diferente ya que es solo un complemento de solo una secuencia, el otro es más para comparar (es como agregarlo, pero no lo estamos, estamos comparando los caracteres dentro del árbol). Reduce la complejidad del espacio ya que está almacenando una secuencia.
Finalmente, el primer algoritmo de MUMmer solo alineó las dos secuencias y saltó a otro paso. Sin embargo, para lograr una mejor cobertura, las secuencias de MUM se están convirtiendo en grupos (lo que significa que es un grupo de MUM que están separados con un número menor de espacios).
MUMmer 3
Según Stefan Kurtz y sus compañeros de equipo, “la mejora técnica más significativa en MUMmer 3.0, es una reescritura completa del código del árbol de sufijos, basado en la representación compacta del árbol de sufijos de” el árbol descrito en el artículo “Reducir el requisito de espacio de árboles de sufijo ”.
Otra mejora fue la relajación de las MUM. Esto significa que ahora el usuario tiene la opción de encontrar todas las coincidencias máximas no únicas, todas las coincidencias que son únicas solo en una secuencia elegida o MUM originales (que son únicos para ambas secuencias). Esto se agregó para evitar algún tipo de subsecuencias faltantes que eran copias de MUM.
MUMmer 4
Según Guillaume y su equipo, hay algunas mejoras adicionales en la implementación y también innovación con el paralelismo de consultas. La primera y mayor mejora es el aumento del límite de tamaño para la secuencia que se está probando. Finalmente, “MUMmer4 ahora incluye opciones para guardar y cargar la matriz de sufijos para una referencia dada” (Marcais et al., 2018). Gracias a esto, el árbol de sufijos se puede construir una vez y volver a construirlo después de ejecutarlo desde el árbol de sufijos guardado.
Software: código abierto
MUMmer tiene software de código abierto. La mejor manera de comenzar a jugar con este paquete es ir al sitio web que se muestra a continuación.
Esta página habla sobre el código abierto, los requisitos y los pasos para la instalación, el proceso para ejecutar el paquete y algunos ejemplos de secuencias en ejecución. Hay más información en este sitio web. Si se atasca, el sitio web tiene información sobre a quién contactar en esos casos. Esta página tiene información valiosa para trabajar con este algoritmo.
Temas relacionados
Hay otros tipos de alineaciones de secuencia, algunos de los temas relacionados se muestran a continuación:
- Editar distancia
- EXPLOSIÓN
- Corbata de moño
- BWA
- Blat
- Color de malva
- LASTZ
- EXPLOSIÓN