Saltar ao contido

Aliñamento múltiple de secuencias: Diferenzas entre revisións

Na Galipedia, a Wikipedia en galego.
Explorar o historial de forma interactiva
← Edición máis vellaEdición máis nova →
Contido eliminado Contido engadido
VisualTexto wiki
Miguelferig (conversa | contribucións)
246.579 edicións
Miguelferig (conversa | contribucións)
246.579 edicións
Liña 39: Liña 39:


Poden atoparse bastantes programas de software nos cales se aplican variantes dos métodos baseados en HMM, e que se caracterizan pola súa escalabilidade e eficiencia, aínda que o uso correcto dun método HMM é máis complexo que o dos métodos progresivos máis comúns. O máis sinxelo é [http://sourceforge.net/project/showfiles.php?group_id=168080 POA] (''Partial-Order Alignment'', Aliñamento de orde parcial).<ref name="grasso">Grasso C, Lee C. (2004). Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. ''Bioinformatics'' 20(10):1546-56.</ref> Un método similar, pero máis xeral, aplícase no paquete [http://www.cse.ucsc.edu/compbio/sam.html SAM] (''Sequence Alignment and Modeling System'', sistema de aliñamento e modelado de secuencia).<ref name=autogenerated1>Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996.</ref> O SAM tense usado como unha fonte de aliñamentos para [[predición de estrutura de proteínas]] ao participar no experimento de predición de estrutura [[CASP]] (de ''Critical Assessment of Techniques for Protein Structure Prediction'', Valoración crítica de técnicas para predición da estructura de proteínas), e para desenvolver unha base de datos de proteínas preditas na especie de [[lévedo]]s ''[[Saccharomyces cerevisiae]]''. Os métodos HMM tamén poden usarse para buscas en bases de datos con [http://web.archive.org/web/http://hmmer.wustl.edu/ HMMer].<ref name="durbin">Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.</ref>
Poden atoparse bastantes programas de software nos cales se aplican variantes dos métodos baseados en HMM, e que se caracterizan pola súa escalabilidade e eficiencia, aínda que o uso correcto dun método HMM é máis complexo que o dos métodos progresivos máis comúns. O máis sinxelo é [http://sourceforge.net/project/showfiles.php?group_id=168080 POA] (''Partial-Order Alignment'', Aliñamento de orde parcial).<ref name="grasso">Grasso C, Lee C. (2004). Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. ''Bioinformatics'' 20(10):1546-56.</ref> Un método similar, pero máis xeral, aplícase no paquete [http://www.cse.ucsc.edu/compbio/sam.html SAM] (''Sequence Alignment and Modeling System'', sistema de aliñamento e modelado de secuencia).<ref name=autogenerated1>Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996.</ref> O SAM tense usado como unha fonte de aliñamentos para [[predición de estrutura de proteínas]] ao participar no experimento de predición de estrutura [[CASP]] (de ''Critical Assessment of Techniques for Protein Structure Prediction'', Valoración crítica de técnicas para predición da estructura de proteínas), e para desenvolver unha base de datos de proteínas preditas na especie de [[lévedo]]s ''[[Saccharomyces cerevisiae]]''. Os métodos HMM tamén poden usarse para buscas en bases de datos con [http://web.archive.org/web/http://hmmer.wustl.edu/ HMMer].<ref name="durbin">Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.</ref>

<!--
== Algoritmos xenéticos e ''annealing'' simulado ==
== Algoritmos xenéticos e ''annealing'' simulado ==
En el intento de producir MSA de calidad de forma más eficiente también se han usado algunas técnicas de optimización estándar en ciencias de la computación inspiradas por procesos físicos (pero que no los reproducen directamente). Una de tales técnicas, los [[Algoritmo genético|algoritmos genéticos]], se han utilizado en la producción de MSA intentando simular, en líneas generales, el hipotético proceso evolutivo que da lugar a la divergencia en el conjunto problema. Este método trabaja rompiendo en fragmentos una serie de posibles MSA y reordenando repetidamente estos fragmentos con la introducción de huecos en diferentes posiciones. Una [[función objetivo]] general se optimiza durante la simulación, normalmente una función de maximización "suma de pares" introducida en los métodos de MSA de programación dinámica. Se ha implementado una técnica para secuencias de proteínas en el programa de software SAGA (''Sequence Alignment by Genetic Algorithm'', alineamiento de secuencias por algoritmo genético),<ref name="notredame2">Notredame C, Higgins DG. (1996). SAGA: sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 24(8):1515-24.</ref> denominándose RAGA su equivalente para ARN.<ref name="notredame3">Notredame C, O'Brien EA, Higgins DG. (1997). RAGA: RNA sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 25(22):4570-80.</ref>
No intento de producir MSA de calidade de forma máis eficiente tamén se usaron algunhas técnicas de optimización estándar en ciencias da computación inspiradas por procesos físicos (pero que non os reproducen directamente). Unha delas son os [[Algoritmo xenético|algoritmos xenéticos]], que se utilizaron na produción de MSA intentando simular, en liñas xerais, o hipotético proceso evolutivo que dá lugar á diverxencia no conxunto problema. Este método traballa rompendo en fragmentos unha serie de posibles MSA e reordenando repetidamente estes fragmentos coa introdución de ocos en diferentes posicións. Unha [[función obxectivo]] xeral optimízase durante a simulación, normalmente unha función de maximización "suma de pares" introducida nos métodos de MSA de programación dinámica. Aplicouse unha técnica para secuencias de proteínas no programa de software SAGA (''Sequence Alignment by Genetic Algorithm'', Aliñamento de secuencias por algoritmo xenético),<ref name="notredame2">Notredame C, Higgins DG. (1996). SAGA: sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 24(8):1515-24.</ref> e denomínsse RAGA o seu equivalente para ARN.<ref name="notredame3">Notredame C, O'Brien EA, Higgins DG. (1997). RAGA: RNA sequence alignment by genetic algorithm. ''Nucleic Acids Res'' 25(22):4570-80.</ref>


Mediante la técnica de ''[[simulated annealing]]'' (tienen relativamente poco éxito en la literatura en castellano traducciones como "temple" o "recocido" simulado), un alineamiento múltiple de secuencias existente, producido por otro método, se refina por una serie de reordenamientos diseñados para encontrar regiones más óptimas del espacio de alineamiento que la ya ocupada por el MSA previo. Al igual que en el método de algoritmos genéticos, en ''simulated annealing'' se maximiza una función objetivo como la suma de pares. Este método utiliza un "factor de temperatura" metafórico que determina el ritmo al cual los reordenamientos avanzan, así como la probabilidad de cada uno de ellos. Un uso típico alterna periodos de altos ritmos de reorganización y relativamente baja probabilidad (para explorar regiones más distantes del espacio de alineamiento), con periodos de bajos ritmos y más altas probabilidades para explorar a fondo mínimos locales cerca de las regiones recientemente “colonizadas”. Este enfoque ha sido implementado en el programa MSASA (''Multiple Sequence Alignment by Simulated Annealing'', alineamiento múltiple de secuencias por ''simulated annealing'').<ref name="kim">Kim J, Pramanik S, Chung MJ. (1994). Multiple sequence alignment using simulated annealing. ''Comput Appl Biosci'' 10(4):419-26.</ref>
Mediante a técnica de ''[[simulated annealing]]'', un aliñamento múltiple de secuencias existente, producido por outro método, refínase por unha serie de reordenamentos deseñados para encontrar rexións máis óptimas do espacio de aliñamento que a xa ocupada polo MSA previo. Igual que no método de algoritmos xenéticos, no ''simulated annealing'' maximízase unha función obxectivo como a suma de pares. Este método utiliza un "factor de temperatura" metafórico que determina o ritmo ao cal avanzan os reordenamentos, e a probabilidade de cada un deles. Un uso típico alterna períodos de altos ritmos de reorganización e relativamente baixa probabilidade (para explorar rexións máis distantes do espazo de aliñamento), con períodos de baixos ritmos e máis altas probabilidades para explorar a fondo mínimos locais preto das rexións recentemente “colonizadas”. Este enfoque foi implementado no programa MSASA (''Multiple Sequence Alignment by Simulated Annealing'', aliñamento múltiple de secuencias por ''simulated annealing'').<ref name="kim">Kim J, Pramanik S, Chung MJ. (1994). Multiple sequence alignment using simulated annealing. ''Comput Appl Biosci'' 10(4):419-26.</ref>


== Descubrimento de motivos ==
== Descubrimento de motivos ==
[[Archivo:Caspase-motif-alignment.png|thumb|500px|Alineamiento de las [[caspasa]]s de [[Drosophila]] coloreado por motivos identificados por MEME. Cuando las posiciones de los motivos y los alineamientos de las secuencias se generan independientemente, a menudo se correlacionan, pero no perfectamente, como en este ejemplo.]]
[[Ficheiro:Caspase-motif-alignment.png|miniatura|500px|Aliñamento das [[caspase]]s de ''[[Drosophila]]'' coloreado por motivos identificados por MEME. Cando as posicións dos motivos e os aliñamentos das secuencias se xeran independentemente, a miúdo correlaciónanse, pero non perfectamente, como neste exemplo.]]


El descubrimiento de motivos, también conocido como análisis de perfiles, es un método de localización de [[Motivo de secuencia|motivos de secuencia]] en MSA globales, y que supone tanto un medio para producir mejores alineamientos múltiples de secuencias como para producir una matriz de puntuación para ser usada en la búsqueda de motivos similares en otras secuencias. Se han desarrollado varios métodos para aislar los motivos, pero todos están basados en la identificación de patrones cortos altamente conservados dentro de un alineamiento mayor, y en la construcción de una matriz, similar a una de sustitución, que refleje la composición de aminoácidos o nucleótidos de cada posición en el supuesto motivo. Los alineamientos se pueden refinar entonces usando estas matrices. En el análisis estándar de perfiles, la matriz incluye entradas para cada posible carácter, así como entradas para huecos.<ref name="mount" /> Alternativamente, los algoritmos estadísticos de descubrimiento de patrones pueden identificar motivos como precursores de MSA, en lugar de como derivados. En muchos casos, cuando el conjunto de secuencias problema contiene sólo un pequeño número de secuencias, o contiene sólo secuencias altamente relacionadas, se añaden [[seudocontador]]es para normalizar la distribución reflejada en la matriz de puntuación. Esto corrige, en particular, entradas en la matriz con probabilidad cero mediante valores pequeños, pero no nulos.
O descubrimento de motivos, tamén coñecido como análise de perfís, é un método de localización de motivos de secuencia en MSA globais, que supón un medio para producir mellores aliñamentos múltiples de secuencias e para producir unha matriz de puntuación para ser usada na busca de motivos similares noutras secuencias. Desenvolvéronse varios métodos para illar os motivos, pero todos están baseados na identificación de patróns curtos altamente conservados dentro dun aliñamento maior, e na construcción dunha matriz, similar a unha de substitución, que reflicta a composición de aminoácidos ou nucleótidos de cada posición no suposto motivo. Os aliñamentos pódense refinar entóns usando estas matrices. Na análise estándar de perfís, a matriz inclúe entradas para cada posible carácter, e entradas para ocos.<ref name="mount" /> Alternativamente, os algoritmos estatísticos de descubrimento de patróns poden identificar motivos como precursores de MSA, en lugar de como derivados. En moitos casos, cando o conxunto de secuencias problema contén só un pequeno número de secuencias, ou contén só secuencias altamente relacionadas, engádense [[pseudocontador]]es para normalizar a distribución reflectida na matriz de puntuación. Isto corrixe, en particular, entradas na matriz con probabilidade cero mediante valores pequenos, pero non nulos.


El análisis de bloques es un método de descubrimiento de motivos que los restringe a regiones sin huecos en el alineamiento. Los bloques se pueden generar desde un MSA o pueden ser extraídos de secuencias sin alinear usando un conjunto precalculado de motivos previamente generado desde familias conocidas de genes.<ref name="henikoff">Henikoff S, Henikoff JG. (1991). Automated assembly of protein blocks for database searching. ''Nucleic Acids Res'' 19:6565-72.</ref> La puntuación de los bloques depende generalmente del espaciado de los caracteres con altas frecuencias, en lugar de recaer sobre el cálculo de una matriz de sustitución explícita. El servidor [http://blocks.fhcrc.org/ BLOCKS] proporciona un método interactivo para localizar tales motivos en secuencias sin alinear.
A análise de bloques é un método de descubrimento de motivos que os restrinxe a rexións sen ocos no aliñamento. Os bloques pódense xerar desde un MSA ou poden ser extraídos de secuencias sen aliñar usando un conxunto precalculado de motivos previamente xerado desde familias coñecidas de xenes.<ref name="henikoff">Henikoff S, Henikoff JG. (1991). Automated assembly of protein blocks for database searching. ''Nucleic Acids Res'' 19:6565-72.</ref> A puntuación dos bloques depende xeralmente do espazado dos caracteres con altas frecuencias, en lugar de recaer sobre o cálculo dunha matriz de substitución explícita. O servidor [http://blocks.fhcrc.org/ BLOCKS] proporciona un método interactivo para localizar tales motivos en secuencias sen aliñar.


Se han implementado comparadores de patrones utilizando tanto el [[algoritmo expectación-maximización]] como el [[muestreo de Gibbs]]. Una de las más comunes herramientas de descubrimiento de motivos, denominada MEME, utiliza expectación-maximización y modelos ocultos de Márkov para generar motivos que luego se usan como herramientas de búsqueda por su compañero MAST en la suite combinada [http://meme.sdsc.edu/meme/intro.html MEME/MAST].<ref name="baileyelkan">Bailey TL, Elkan C.(1994). Fitting a mixture model by expectation maximization to discover motifs in biopolymers. Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology, pp. 28-36, AAAI Press, Menlo Park, California.</ref><ref name="baileygribskov">Bailey TL, Gribskov M. (1998). Combining evidence using p-values: application to sequence homology searches. ''Bioinformatics''14:48-54.</ref>
Aplicáronse comparadores de patróns utilizando tanto o [[algoritmo expectación-maximización]] coma a [[mostraxe de Gibbs]]. Unha das ferramentas máis comúns de descubrimento de motivos, denominada MEME, utiliza expectación-maximización e modelos ocultos de Markov para xerar motivos que logo se usan como ferramentas de busca polo seu compañeiro MAST na suite combinada [http://meme.sdsc.edu/meme/intro.html MEME/MAST].<ref name="baileyelkan">Bailey TL, Elkan C.(1994). Fitting a mixture model by expectation maximization to discover motifs in biopolymers. Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology, pp. 28-36, AAAI Press, Menlo Park, California.</ref><ref name="baileygribskov">Bailey TL, Gribskov M. (1998). Combining evidence using p-values: application to sequence homology searches. ''Bioinformatics''14:48-54.</ref>
-->


== Notas ==
== Notas ==

Revisión como estaba o 3 de xuño de 2015 ás 16:37

As primeiras 90 posicións dun aliñamento múltiple de secuencias de exemplos da proteína ribosómica ácida P0 (L10E) de varios organismos. Xerado con ClustalX.
Aliñamento múltiple de 27 secuencias da proteína hemaglutinina do virus da gripe aviaria, coloreado segundo a conservación de residuos (máis escuro canta maior conservación; arriba) e as súas propiedades químicas (abaixo).

Un aliñamento múltiple de secuencias ou aliñamento de secuencias múltiples (MSA, nas súas siglas en inglés, de Multiple Sequence Alignment) é un aliñamento das secuencias de tres ou máis secuencias biolóxicas, xeralmente proteínas, ADN ou ARN (secuencias de aminoácidos ou de nucleótidos). En xeral, asúmese que as diversas secuencias a examinar que se introducen como entrada (conxunto problema) teñen unha relación evolutiva, comparten unha liñaxe e descenden dun antepasado común. Do MSA resultante, pode inferirse a homoloxía entre esas moléculas, e pode realizarse unha análise filoxenética para avaliar as orixes evolutivas compartidas polas secuencias. As representacións visuais do aliñamento poñen de manifesto mutacións tales como mutacións puntuais (un só cambio de aminoácidos ou nucleótidos) que aparecen como diferentes caracteres nunha soa columna do aliñamento, e a inserción ou supresión de mutacións (ou indeis) que aparecen como ocos nunha ou varias das secuencias da aliñación. O aliñamento múltiple de secuencias utilízsase a miúdo para avaliar a conservación dos dominios proteicos, as estruturas terciarias e secundarias das moléculas, e mesmo aminoácidos ou nucleótidos individuais.

Co termo aliñamento múltiple de secuencias tamén se fai referencia ao proceso de aliñalas como un conxunto de secuencias. Como pode ser difícil aliñar a man tres ou máis secuencias de lonxitude bioloxicamente relevante, e case sempre leva moito tempo, utilízanse algoritmos computacionais para producir e analizar os aliñamentos. Os MSA requiren metodoloxías máis sofisticadas que os aliñamento de pares porque son computacionalmente máis complexos de producir. A maior parte dos programas de aliñamento múltiple de secuencias usan métodos heurísticos en lugar de optimización global, porque identificar o aliñamento óptimo entre máis dunhas poucas secuencias de lonxitude moderada é moi costoso computacionalmente.

Programación dinámica e complexidade computacional

O método máis directo para producir aliñamentos múltiples de secuencias utiliza a técnica de programación dinámica para identificar a solución de aliñamento globalmente óptima. Para as proteínas, este método supón normalmente dous conxuntos de parámetros: unha penalización por oco (gap) e unha matriz de substitución que asigna puntuacións ou probabilidades ao aliñamento de cada posible par de aminoácidos baseadas na semellanza das propiedades químicas destes ou na probabilidade evolutiva da mutación. Para secuencias de nucleótidos pode usarse unha matriz de substitución, mais dado que só hai catro caracteres estándar posibles (A, T, G, C) por secuencia, e que os nucleótidos individuais non difiren moito na súa probabilidade de substitución, os parámetros para secuencias de ADN e ARN consisten, normalmente, nunha penalización por gap, unha puntuación positiva para coincidencias de caracteres, e unha puntuación negativa para desigualdades.

Para n secuencias individuais, o método require construír o equivalente n-dimensional da matriz formada no aliñamento estándar de pares de secuencias da programación dinámica. Desta forma, o espazo de busca increméntase exponencialmente conforme se incrementa n, dependendo tamén fortemente da lonxitude da secuencia. Atopar desta forma o óptimo global para n secuencias é un problema dos denominados NP-completos.[1][2] Os métodos para reducir o espazo de busca efectuando inicialmente aliñamentos de pares mediante programación dinámica sobre cada par de secuencias no conxunto problema, e buscando só o espazo solución preto destes resultados (encontrando de forma efectiva a intersección entre traxectorias locais nos arredores inmediatos de cada solución óptima de aliñamento por pares) representan a técnica de programación dinámica máis eficiente. O método denominado "suma de pares" utilízase co software MSA, pero non é aínda práctico para a maioría de aplicacións de aliñamento múltiple de secuencias que requiren o aliñamento simultáneo de ducias (e mesmo de varios centenares) de secuencias. Os métodos de programación dinámica só se usan agora cando cómpre facer un aliñamento de moi alta calidade entre un pequeno número de secuencias, e como benchmark estándar na avaliación de técnicas heurísticas novas ou melloradas.

Construción progresiva do aliñamento

Un método para realizar unha busca heurística do aliñamento é a técnica progresiva (tamén coñecida como método xerárquico ou de árbore) que constrúe un aliñamento múltiple final realizando primeiro unha serie de aliñamentos de pares sobre secuencias sucesivamente menos emparentadas. Tales métodos comezan aliñando en primeiro lugar as dúas secuencias máis cercanamente relacionadas, para seguir aliñando sucesivamente a seguinte secuencia do conxunto problema máis emparentada co aliñamento producido no paso previo. O par inicial "máis relacionado", ou emparentado, determínase mediante un método eficiente de categorización (ou clustering) tal como o neighbour-joining, baseado nunha simple busca heurística do conxunto problema cunha ferramenta como FASTA. As técnicas progresivas, por tanto, constrúen automaticamente tanto unha árbore filoxenética coma un aliñamento.

Unha limitación importante dos métodos progresivos é a súa forte dependencia da asignación inicial do parentesco entre as secuencias, e da calidade do aliñeamento inicial. Deste modo, os métodos son sensibles tamén á distribución das secuencias no conxunto problema: o rendemento mellora cando a cuantificación da estrutura do parentesco entre as secuencias problema compón un gradiente relativamente suave en lugar de encontrarse en categorías afastadas. Tamén se degrada significativamente o rendemento cando todas as secuencias do conxunto teñen unha relación bastante distante, xa que entón son máis probables as imprecisións no aliñamento inicial. Os métodos progresivos máis modernos modifican a súa función de puntuación cunha función de ponderación secundaria que asigna individualmente factores de escala a membros do conxunto problema de forma non liñal, baseada na súa distancia filoxenética aos seus veciños máis próximos. Unha elección asisada dos pesos pode axudar na avaliación das relacións e mitigar os efectos de aliñamentos iniciais relativamente pobres en instantes temperáns da progresión.

Os métodos de aliñamento progresivo son dabondo eficientes como para aplicalos a gran escala para moitas secuencias, e execútanse a miúdo en servidores web acesibles publicamente, polo que os usuarios non necesitan instalar localmente as aplicacións de interese. Uns métodos de aliñamento progresivo moi utilizados son os da familia Clustal,[3] especialmente a variante ponderada ClustalW,[4] cuyo acceso se proporciona en un buen número de portales web, incluyendo GenomeNet, EBI e EMBNet. Hai diferentes portais ou aplicacións que poden variar a interfaz co usuario e facer accesibles a este diferentes parámetros. O uso de Clustal está moi estendido para a construción de árbores filoxenéticas e como input para a predición da estrutura de proteínas por medio da modelaxe por homoloxía.

Outro método común de aliñamento progresivo denominado T-Coffee[5] é máis lento que Clustal e os seus derivados, mais xeralmente produce aliñamentos máis precisos para conxuntos de secuencias distantemente emparentadas. T-Coffee calcula aliñamentos de pares combinando o aliñamento directo do par con aliñamentos indirectos que aliñan cada secuencia do par cunha terceira. Usa a saída de Clustal así como outro programa de aliñamento local, LALIGN, que encontra rexións múltiples de aliñamento local entre dúas secuencias. Os aliñamintos e a árbore filoxenética resultante úsanse como guía para producir factores de ponderación novos e máis precisos.

Como os métodos progresivos son heurísticos e, por tanto, non garanten a converxencia a un óptimo global, a calidade do aliñamento pode ser difícil de avaliar, e a súa verdadeira significación biolóxica pode ser escura. Un método semiprogresivo moi recente que mellora a calidade do aliñamento e que non utiliza unha heurística "con perdas" á vez que se executa en tempo polinómico[6] aplicouse no programa PSAlign.

Métodos iterativos

Un conxunto de métodos para producir aliñamentos múltiples de secuencias que reducen os erros inherentes aos métodos progresivos son os clasificados como “iterativos”, xa que traballan de forma similar aos métodos progresivos, pero realiñan repetidamente as secuencias iniciais ademais de engadir novas secuencias ao MSA en crecemento. Unha razón pola que os métodos progresivos son tan fortemente dependentes da alta calidad do aliñamento inicial é que estes aliñamentos se incorporan sempre ao resultado final; isto é, unha vez que unha secuencia foi aliñada dentro do MSA, o seu aliñamento non volve a ser considerado. Este enfoque mellora a eficiencia a costa da precisión. En contraste, os métodos iterativos poden volver a aliñamentos de pares previamente calculados (ou sub-MSAs) incorporando subconxuntos da secuencia problema como un medio de optimización dunha función obxectivo xeral, tal como encontrar unha puntuación de aliñamento de alta calidade.

Aplicáronse unha variedade de métodos de iteración sutilmente diferentes, que se poden encontrar en diferentes paquetes de software. Existen revisións e comparacións útiles, pero evitan, xeralmente, elixir algunha das técnicas como a "mellor".[7]

O paquete PRRN/PRRP utiliza un algoritmo hill climbing (ascenso da colina) para optimizar a súa puntuación de aliñamento do MSA[8] e corrixir iterativamente tanto as ponderacións do aliñamento como as rexións localmente diverxentes (con ocos) do aliñamento múltiple de secuencias en crecemento.[9] O PRRP actúa mellor cando refina un aliñamento previamente construído por un método máis rápido.[9]

Outro programa iterativo chamado DIALIGN, segue unha estratexia inusual ao concentrarse estreitamente en aliñamentos locais entre subsegmentos ou secuencias motivo sen introducir unha penalización por oco.[10] Consegue o aliñamento de motivos individuais cunha representación matricial similar a unha gráfica de matriz de puntos nun aliñamentos de pares. Un método alternativo que utiliza aliñamentos locais rápidos como puntos de referencia ou "sementes" para un procedemento máis lento de aliñamento global aplícase na suite CHAOS/DIALIGN.[11]

Un terceiro método de uso común baseado na iteración, chamado MUSCLE (de multiple sequence alignment by log-expectation, ou aliñamento múltiple de secuencias por log-esperanza; este último termo corresponde a unha función de puntuación non común baseada na esperanza matemática, e resultado de modificar a función log-average ou log-media), mellora os resultados en relación aos métodos progresivos ao obter unha medida máis precisa da distancia para valorar o parentesco de dúas secuencias.[12] A medición da distancia actualízase entre as etapas da iteración (porén, na súa forma orixinal, MUSCLE contiña só dous ou tres iteracións, dependendo de se se activaba ou non o refinamento).

Modelos de Markov ocultos

Os modelos de Markov ocultos (ou HMM, do inglés Hidden Markov Models) son modelos probabilísticos que asignan probabilidades a todas as posibles combinacións de ocos, coincidencias e diferenzas para determinar o máis probable aliñamento múltiple de secuencias ou conxunto de posibles MSA. Os HMM poden producir unha saída única coa maior puntuación, pero tamén poden xerar unha familia de aliñamentos posibles que poidan avaliarse en canto á súa importancia biolóxica. Dado que os modelos ocultos de Markov son probabilísticos, non producen a mesma solución cada vez que se executan sobre o mesmo conxunto de datos; desta forma, non poden garantir converxer ao aliñamento óptimo. Os HMM poden producir aliñamentos tanto locais coma globais. Aínda que os métodos baseados nestes modelos foron desenvolvidos recentemente, ofrecen melloras significativas na velocidade computacional, especialmente para secuencias que conteñen rexións solapadas.[9]

Os métodos típicos baseados en HMM traballan representando un MSA baixo a forma de grafo dirixido acíclico, coñecido como un grafo de orde parcial, e que consiste nunha serie de nodos que representan posibles entradas nas columnas dun aliñamento múltiple de secuencias. Nesta representación, unha columna que estea absolutamente conservada (é dicir, que todas as secuencias no MSA compartan un carácter determinado nesa posición en particular) codifícase como un único nodo con tantas conexións saíntes coma posibles caracteres haxa na seguinte columna do aliñamento. Nos termos dun típico modelo oculto de Markov, os estados observados son as columnas individuais do aliñamento, e os estados "ocultos" representan a suposta secuencia ancestral desde a cal se presume que descenden as secuencias do conxunto problema. Unha variante de busca eficiente do método de programación dinámica, coñecida como algoritmo de Viterbi, úsase xeralmente para aliñar sucesivamente o MSA en crecemento coa seguinte secuencia do conxunto problema para xerar un novo MSA.[13] Isto é diferente dos métodos de aliñamento progresivo porque o aliñamento das secuencias previas se actualiza en cada adición dunha nova secuencia. Porén, como nos métodos progresivos, esta técnica pode verse influenciada pola orde na cal as secuencias do conxunto problema son integradas no aliñamento, especialmente cando as secuencias están relacionadas distantemente.[9]

Poden atoparse bastantes programas de software nos cales se aplican variantes dos métodos baseados en HMM, e que se caracterizan pola súa escalabilidade e eficiencia, aínda que o uso correcto dun método HMM é máis complexo que o dos métodos progresivos máis comúns. O máis sinxelo é POA (Partial-Order Alignment, Aliñamento de orde parcial).[14] Un método similar, pero máis xeral, aplícase no paquete SAM (Sequence Alignment and Modeling System, sistema de aliñamento e modelado de secuencia).[15] O SAM tense usado como unha fonte de aliñamentos para predición de estrutura de proteínas ao participar no experimento de predición de estrutura CASP (de Critical Assessment of Techniques for Protein Structure Prediction, Valoración crítica de técnicas para predición da estructura de proteínas), e para desenvolver unha base de datos de proteínas preditas na especie de lévedos Saccharomyces cerevisiae. Os métodos HMM tamén poden usarse para buscas en bases de datos con HMMer.[16]

Algoritmos xenéticos e annealing simulado

No intento de producir MSA de calidade de forma máis eficiente tamén se usaron algunhas técnicas de optimización estándar en ciencias da computación inspiradas por procesos físicos (pero que non os reproducen directamente). Unha delas son os algoritmos xenéticos, que se utilizaron na produción de MSA intentando simular, en liñas xerais, o hipotético proceso evolutivo que dá lugar á diverxencia no conxunto problema. Este método traballa rompendo en fragmentos unha serie de posibles MSA e reordenando repetidamente estes fragmentos coa introdución de ocos en diferentes posicións. Unha función obxectivo xeral optimízase durante a simulación, normalmente unha función de maximización "suma de pares" introducida nos métodos de MSA de programación dinámica. Aplicouse unha técnica para secuencias de proteínas no programa de software SAGA (Sequence Alignment by Genetic Algorithm, Aliñamento de secuencias por algoritmo xenético),[17] e denomínsse RAGA o seu equivalente para ARN.[18]

Mediante a técnica de simulated annealing, un aliñamento múltiple de secuencias existente, producido por outro método, refínase por unha serie de reordenamentos deseñados para encontrar rexións máis óptimas do espacio de aliñamento que a xa ocupada polo MSA previo. Igual que no método de algoritmos xenéticos, no simulated annealing maximízase unha función obxectivo como a suma de pares. Este método utiliza un "factor de temperatura" metafórico que determina o ritmo ao cal avanzan os reordenamentos, e a probabilidade de cada un deles. Un uso típico alterna períodos de altos ritmos de reorganización e relativamente baixa probabilidade (para explorar rexións máis distantes do espazo de aliñamento), con períodos de baixos ritmos e máis altas probabilidades para explorar a fondo mínimos locais preto das rexións recentemente “colonizadas”. Este enfoque foi implementado no programa MSASA (Multiple Sequence Alignment by Simulated Annealing, aliñamento múltiple de secuencias por simulated annealing).[19]

Descubrimento de motivos

Aliñamento das caspases de Drosophila coloreado por motivos identificados por MEME. Cando as posicións dos motivos e os aliñamentos das secuencias se xeran independentemente, a miúdo correlaciónanse, pero non perfectamente, como neste exemplo.

O descubrimento de motivos, tamén coñecido como análise de perfís, é un método de localización de motivos de secuencia en MSA globais, que supón un medio para producir mellores aliñamentos múltiples de secuencias e para producir unha matriz de puntuación para ser usada na busca de motivos similares noutras secuencias. Desenvolvéronse varios métodos para illar os motivos, pero todos están baseados na identificación de patróns curtos altamente conservados dentro dun aliñamento maior, e na construcción dunha matriz, similar a unha de substitución, que reflicta a composición de aminoácidos ou nucleótidos de cada posición no suposto motivo. Os aliñamentos pódense refinar entóns usando estas matrices. Na análise estándar de perfís, a matriz inclúe entradas para cada posible carácter, e entradas para ocos.[9] Alternativamente, os algoritmos estatísticos de descubrimento de patróns poden identificar motivos como precursores de MSA, en lugar de como derivados. En moitos casos, cando o conxunto de secuencias problema contén só un pequeno número de secuencias, ou contén só secuencias altamente relacionadas, engádense pseudocontadores para normalizar a distribución reflectida na matriz de puntuación. Isto corrixe, en particular, entradas na matriz con probabilidade cero mediante valores pequenos, pero non nulos.

A análise de bloques é un método de descubrimento de motivos que os restrinxe a rexións sen ocos no aliñamento. Os bloques pódense xerar desde un MSA ou poden ser extraídos de secuencias sen aliñar usando un conxunto precalculado de motivos previamente xerado desde familias coñecidas de xenes.[20] A puntuación dos bloques depende xeralmente do espazado dos caracteres con altas frecuencias, en lugar de recaer sobre o cálculo dunha matriz de substitución explícita. O servidor BLOCKS proporciona un método interactivo para localizar tales motivos en secuencias sen aliñar.

Aplicáronse comparadores de patróns utilizando tanto o algoritmo expectación-maximización coma a mostraxe de Gibbs. Unha das ferramentas máis comúns de descubrimento de motivos, denominada MEME, utiliza expectación-maximización e modelos ocultos de Markov para xerar motivos que logo se usan como ferramentas de busca polo seu compañeiro MAST na suite combinada MEME/MAST.[21][22]

Notas

  1. ↑ Wang L, Jiang T. (1994) On the complexity of multiple sequence alignment. J Comput Biol 1:337-348.
  2. ↑ Just W. (2001). Computational complexity of multiple sequence alignment with SP-score. J Comput Biol 8(6):615-23.
  3. ↑ Higgins DG, Sharp PM. (1988). CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. Gene 73(1):237-44.
  4. ↑ Thompson JD, Higgins DG, Gibson TJ. (1994). CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. Nucleic Acids Res 22:4673-4680.
  5. ↑ Notredame C, Higgins DG, Heringa J. (2000). T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol 302(1):205-17.
  6. ↑ Sze SH, Lu Y, Yang Q. (2006). A polynomial time solvable formulation of multiple sequence alignment. J Comput Biol 13(2):309-19.
  7. ↑ Hirosawa M, Totoki Y, Hoshida M, Ishikawa M. (1995). Comprehensive study on iterative algorithms of multiple sequence alignment. Comput Appl Biosci 11:13-18.
  8. ↑ Gotoh O. (1996). Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. J Mol Biol 264(4):823-38.
  9. ↑ 9,0 9,1 9,2 9,3 9,4 Mount DM. (2004). Bioinformatics: Sequence and Genome Analysis 2nd ed. Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY.
  10. ↑ Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B. (2003) Fast and sensitive multiple alignment of large genomic sequences. BMC Bioinformatics 4:66.
  11. ↑ Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B. (2003) Fast and sensitive multiple alignment of large genomic sequences BMC Bioinformatics 4:66.
  12. ↑ Edgar RC. (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research 32(5), 1792-97.
  13. ↑ Hughey R, Krogh A. (1996). Hidden Márkov models for sequence analysis: extension and analysis of the basic method. CABIOS 12(2):95-107.
  14. ↑ Grasso C, Lee C. (2004). Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. Bioinformatics 20(10):1546-56.
  15. ↑ Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996.
  16. ↑ Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.
  17. ↑ Notredame C, Higgins DG. (1996). SAGA: sequence alignment by genetic algorithm. Nucleic Acids Res 24(8):1515-24.
  18. ↑ Notredame C, O'Brien EA, Higgins DG. (1997). RAGA: RNA sequence alignment by genetic algorithm. Nucleic Acids Res 25(22):4570-80.
  19. ↑ Kim J, Pramanik S, Chung MJ. (1994). Multiple sequence alignment using simulated annealing. Comput Appl Biosci 10(4):419-26.
  20. ↑ Henikoff S, Henikoff JG. (1991). Automated assembly of protein blocks for database searching. Nucleic Acids Res 19:6565-72.
  21. ↑ Bailey TL, Elkan C.(1994). Fitting a mixture model by expectation maximization to discover motifs in biopolymers. Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology, pp. 28-36, AAAI Press, Menlo Park, California.
  22. ↑ Bailey TL, Gribskov M. (1998). Combining evidence using p-values: application to sequence homology searches. Bioinformatics14:48-54.

Véxase tamén

Outros artigos

Bibliografía

  • Duret, L.; S. Abdeddaim (2000). "Multiple alignment for structural functional or phylogenetic analyses of homologous sequences". En D. Higgins and W. Taylor. Bioinformatics sequence structure and databanks. Oxford: Oxford University Press.  A referencia usa o parámetro obsoleto |coautores= (Axuda)
  • Notredame, C. (2002). "Recent progresses in multiple sequence alignment: a survey". Pharmacogenomics 31 (1): 131 –– 144. 
  • Thompson, J. D.; F. Plewniak and O. Poch (1999). "A comprehensive comparison of multiple sequence alignment programs". Nucleic Acids Research 27 (13): 12682––2690.  A referencia usa o parámetro obsoleto |coautores= (Axuda)
  • Wallace, I.M.; Blackshields G and Higgins DG. (2005). "Multiple sequence alignments". Curr Opin Struct Biol 15 (3): 261–6.  A referencia usa o parámetro obsoleto |coautores= (Axuda)
  • Notredame, C (2007). "Recent evolutions of multiple sequence alignment algorithms". PLOS Computational Biology 8 (3): e123. 

Ligazóns externas

Traído desde «https://gl.wikipedia.org/w/index.php?title=Aliñamento_múltiple_de_secuencias&oldid=3566036»