MUSCLE (software de alineación)

Edgar se graduó en 1982 de University College London, Licenciado en Física, Doctor en Física de Partículas. ^{[ 4 ]} Tras su graduación, se dedicó al desarrollo de software y fundó su propia empresa, Parity Software, en 1988. ^{[ 4 ]} En 2001, comenzó a trabajar con algoritmos de codificación después de asistir a un seminario en la Universidad de California, Berkeley. ^{[ 5 ]} Desde 2001 hasta la actualidad, Edgar ha contribuido o ha sido el único creador de múltiples programas de software, incluidos MUSCLE y USEARCH. ^{[ 4 ]} Ha escrito un total de 96 artículos en el campo de la biología computacional desde 2002 hasta la actualidad, siendo su artículo más reciente Discovery and Validation of Alternatives to VSV-G for Pseudotyping of Lentiviral Vectors for In Vivo Delivery of Anti-Tumor Transgenes . Hasta abril de 2025, su trabajo ha sido citado más de 143.126 veces. ^{[ 6 ]} Los dos artículos originales publicados sobre MUSCLE han sido citados más de 58.979 veces en conjunto. El artículo “MUSCLE: alineación de secuencias múltiples con alta precisión y alto rendimiento” ^{[ 1 ]} ha recibido más de 49.052 citas, ^{[ 6 ]} mientras que “MUSCLE: un método de alineación de secuencias múltiples con complejidad espacial y de tiempo reducida” ^{[ 2 ]} ha sido citado más de 9.936 veces. ^{[ 6 ]}

A finales de 2021, Edgar lanzó Muscle5 (también conocido como Muscle v5), una versión actualizada del software MUSCLE. Introduce varias innovaciones destinadas a mejorar la precisión de la alineación y reducir el sesgo presente en otros algoritmos MSA . Las herramientas tradicionales como Clustal Omega , MAFFT y versiones anteriores de MUSCLE se basan en estrategias de alineación progresiva que producen una única alineación. Muscle5, en cambio, genera un conjunto de alineaciones de alta precisión perturbando un modelo oculto de Markov y permutando su árbol guía. En esencia, el algoritmo es una reimplementación paralela de ProbCons y está diseñado para escalar eficientemente a grandes conjuntos de datos. Muscle5 ha demostrado un rendimiento superior en pruebas comparativas en comparación con los principales métodos MSA en varios conjuntos de datos, incluidos BAliBASE, BRAliBASE y PREFAB. ^{[ 3 ]}

Una innovación clave en Muscle5 es el uso de conjuntos de alineación, que proporcionan métricas imparciales de confianza en las alineaciones. Cada MSA individual (réplica) en el conjunto utiliza parámetros fijos pero elegidos independientemente para el modelo oculto de Markov y el árbol guía, lo que permite promediar los resultados en un conjunto diverso de réplicas. Esto permite a los biólogos evaluar la sensibilidad de sus análisis posteriores a la incertidumbre de la alineación comparando los resultados en todo el conjunto. ^{[ 3 ]}

En esta primera etapa, el algoritmo genera un alineamiento múltiple, priorizando la velocidad sobre la precisión. Este paso comienza calculando la distancia k-mer para cada par de secuencias de entrada, creando así una matriz de distancias . UPGMA agrupa esta matriz para generar un árbol binario . A partir de este árbol, se construye un alineamiento progresivo, comenzando con la creación de perfiles para cada hoja. Para cada nodo, se realiza un alineamiento por pares de los dos perfiles hijos, asignando un nuevo perfil a dicho nodo. Este proceso continúa hasta obtener un alineamiento múltiple de todas las secuencias de entrada en la raíz del árbol.

Dado${\displaystyle N}$secuencias de entrada y${\displaystyle L}$como la longitud promedio de la secuencia, la complejidad temporal de la etapa progresiva del borrador es

${\displaystyle O(N^{2}\cdot L+N\cdot L^{2})}$.

Aquí, el par${\displaystyle k}$El cálculo de la distancia -mer se calcula como${\displaystyle O(N^{2}\cdot L)}$y los pasos de alineación progresiva toman${\displaystyle O(N\cdot L^{2})}$, dónde${\displaystyle O}$denota la cota superior asintótica. La complejidad espacial es${\displaystyle O(N\cdot L)}$ya que el algoritmo mantiene perfiles y alineaciones para cada secuencia a lo largo del árbol. ^{[ 1 ]}

Esta etapa se centra en obtener un árbol más óptimo calculando la distancia de Kimura para cada par de secuencias de entrada utilizando el alineamiento de secuencias múltiples obtenido en la primera etapa, y crea una segunda matriz de distancias. UPGMA agrupa esta matriz de distancias para obtener un segundo árbol binario. Se realiza un alineamiento progresivo para obtener un alineamiento de secuencias múltiples similar al de la primera etapa, pero se optimiza calculando únicamente los alineamientos en subárboles cuyo orden de ramificación ha cambiado con respecto al primer árbol binario, lo que resulta en un alineamiento más preciso.

En la segunda etapa se realizan alineamientos refinados recalculando un árbol más preciso mediante la distancia de Kimura. Por lo tanto, el análisis del algoritmo implica los subprocedimientos iniciales de cálculos de distancia por pares y alineación progresiva; sin embargo, se realizan optimizaciones en el cálculo limitando la realineación solo a aquellos subárboles con órdenes de ramificación alterados. La optimización se presenta de la siguiente manera:

${\displaystyle O(N^{2}\cdot L+m\cdot L^{2})}$,

donde la variable${\displaystyle m}$denota el número de realineaciones de subárboles. De manera similar, la complejidad espacial es

${\displaystyle O(N\cdot L)}$,

ya que los perfiles y alineamientos de las secuencias de entrada se almacenan para el proceso de alineación progresiva. ^{[ 1 ]}

En esta etapa final, se selecciona una arista del segundo árbol, recorriendo las aristas en orden decreciente de distancia desde la raíz. La arista seleccionada se elimina, dividiendo el árbol en dos subárboles. A continuación, se calcula el perfil de la alineación múltiple para cada subárbol. Se genera una nueva alineación de secuencias múltiples realineando los perfiles de los subárboles. Si la puntuación SP mejora, se conserva la nueva alineación; de lo contrario, se descarta. El proceso de eliminación de una arista y alineación se repite hasta la convergencia o hasta alcanzar un límite definido por el usuario.

La complejidad temporal de la etapa de refinamiento se expresa como:${\displaystyle O(k\cdot L^{2})}$. Aquí,${\displaystyle k}$denota el número de eliminaciones de aristas y${\displaystyle L}$denota la longitud promedio de la secuencia, donde el realineamiento de los perfiles del subárbol sigue siendo el costo dominante por iteración. La complejidad espacial permanece igual que la dada en las etapas uno y dos:${\displaystyle O(N\cdot L)}$Dado que se produce el mismo proceso de refinamiento iterativo, la complejidad asintótica sigue siendo polinómica, ya que el término dominante crece linealmente con respecto al número de pasos de refinamiento.

En comparación, el algoritmo CLUSTALW incluye un paso de refinamiento iterativo optimizado de tal manera que se produce una realineación selectiva del árbol para maximizar la precisión de la alineación sin repetir todo el proceso. Sin embargo, la complejidad temporal y espacial no cambia para este paso de refinamiento iterativo optimizado. La complejidad temporal es${\displaystyle O(k\cdot L^{2})}$, dónde${\displaystyle k}$es el número de pasos de refinamiento y${\displaystyle L}$es la longitud de alineación promedio. La complejidad espacial se da como${\displaystyle O(N\cdot L)}$, nuevamente, para perfiles de alineación y datos de secuencia para todos${\displaystyle N}$secuencias de entrada. ^{[ 1 ] [ 2 ]}

En las dos primeras etapas del algoritmo, la complejidad temporal es O( N²L + NL² ^{) , y} la complejidad espacial es O( N² + NL + L² ⁾ . La etapa de refinamiento añade a la complejidad temporal otro término, O( N³L ) . ^{[ 1 ] MUSCLE se usa a} menudo como reemplazo de Clustal , ya que suele (pero no siempre) proporcionar mejores alineamientos de secuencias ^. Dependiendo de las opciones elegidas, MUSCLE es significativamente más rápido que Clustal, sobre todo para alineamientos más grandes. ^{[ 1 ] [ 2 ]}

La mayoría de los programas modernos de alineación de secuencias múltiples son generalmente aceptados al presentar secuencias alineadas, pero existen algunas diferencias entre ellos. La principal diferencia radica en el método utilizado para alinear las secuencias. Por ejemplo, T-COFFEE y Clustal utilizan el método progresivo, mientras que MUSCLE y MAFFT emplean el método iterativo de alineación. ^{[ 9 ]} Estos dos métodos difieren en su capacidad para manejar secuencias de baja similitud, siendo el método iterativo el que proporciona resultados más precisos. Otra diferencia entre los métodos reside en sus necesidades computacionales.

Originalmente, MUSCLE tenía demandas de CPU intermedias en comparación con otros programas, pero definitivamente eran más altas que los métodos progresivos. ^{[ 1 ]} Las comparaciones con versiones modernas de programas MSA revelan que muchos son bastante similares en capacidades. Los alineamientos se evaluaron en función de su suma de pares (SP), que es la coincidencia correcta de dos nucleótidos/aminoácidos en dos secuencias, y sus columnas totales (TC), que es la columna de coincidencia dividida por el total de columnas. En estos casos, MUSCLE fue promedio en su capacidad para maximizar pares y columnas coincidentes, siendo ligeramente peor que ProbCons , T-Coffee, Probalign y MAFFT. ^{[ 10 ]} Fuera de las puntuaciones de alineación, MUSCLE fue menos exigente computacionalmente tanto en el tiempo de ejecución de la alineación como en la demanda de memoria.