Métodos de matriz de puntos

Una matriz de puntos d'ADN del factor de trescripción deu de cinc nel ser humanu (GenBank ID NM_002383), amosando autosimilitud rexonal. La diagonal principal representa l'alliniadura de la secuencia consigo mesma; les llinies fora d'esta diagonal representen patrones similares o repetitivos dientro de la secuencia. Ye un exemplu típicu de gráfica recurrente.

L'enfoque de matriz de puntos (o matrix-dot), que implícitamente produz una familia d'alliniadures pa rexones individuales de la secuencia, ye cualitativu y simple, a pesar de que consume enforma tiempu p'analís a gran escala. Ye fácil identificar visualmente determinaes carauterístiques de la secuencia (tales como insertamientos, borraos, repeticiones, o repeticiones invertíes) nuna gráfica de matriz de puntos. Pa construyir una gráfica de matriz de puntos, los dos secuencies asitiar a lo llargo de la fila cimera y de la columna que ta más a la izquierda de la matriz de dos dimensiones y asítiase un puntu en cualquier llugar nel que los calteres nes columnes correspondientes coincidan (esta ye una típica gráfica recurrente). Delles implementaciones varien el tamañu o la intensidá de los puntos en función del grau de semeyanza de los dos calteres, pa dar cabida a les sustituciones calteníes. La gráfica de puntos de secuencies bien estrechamente rellacionaes apaez como una única llinia a lo llargo de la diagonal principal de la matriz .

Les gráfiques de puntos tamién pueden utilizase pa evaluar repetitividad nuna sola secuencia: una secuencia se gráfica contra sigo mesma, y les rexones que comparten semeyances significatives van apaecer como llinies fora de la diagonal principal. Esti efeutu puede asoceder cuando una proteína consta de múltiples dominios estructurales similares.

Programación dinámica

La téunica de programación dinámica puede aplicase pa producir alliniadures globales por aciu l'algoritmu de Needleman-Wunsch, según alliniadures locales por aciu l'algoritmu de Smith-Waterman. Nun usu habitual, nes alliniadures de proteínes utiliza una matriz de sustitución p'asignar puntuaciones a les coincidencies y a les diferencies ente aminoácidos, y una penalización por gap (lliteralmente buecu, anque en bona parte de la lliteratura en castellán utiliza'l vocablu inglés) al faer coincidir un aminoácidu d'una secuencia con un buecu n'otra. N'alliniadures d'ADN y ARN puede usase una matriz de puntuaciones, pero na práctica, de cutiu, asígnase a cencielles una puntuación positiva a les coincidencies, una negativa a les diferencies, y otra penalización negativa a los gaps. (Na programación dinámica estándar la puntuación de la posición de cada aminoácidu ye independiente de la identidá de los sos vecinos, polo que los efeutos del apilamientu de bases nun se tomen en cuenta. Sicasí, ye posible faelo modificando l'algoritmu.)

La programación dinámica pue ser útil na alliniadura de nucleótidos con secuencies de proteínes, una xera complicada pola necesidá de tomar en considerancia les mutaciones con cambéu (insertamientos o borraos, de normal). La busca del marcu abiertu de llectura apurre una serie d'alliniadures de pares locales o globales ente una secuencia de nucleótidos a investigar (secuencia problema) y un conxuntu de busca de secuencies de proteínes, o viceversa. A pesar de que'l métodu ye bien lentu, la so habilidá pa evaluar la compensación de los marcos de llectura pa un númberu arbitrariu de nucleótidos convertir en preséu pa secuencies que contengan un bon númberu d'indels, que pueden ser bien difíciles d'alliniar con métodos heurísticos más eficientes. Na práctica, el métodu rique una bona cantidá de potencia de cómputu, o un sistema que la so arquiteutura tea especializada en programación dinámica. Les suites BLAST y EMBOSS apurren ferramientes básiques pa crear alliniadures afeches (anque dalgún d'estos enfoques saca ventaya de los efeutos llaterales de la capacidá de busca de secuencies de les ferramientes). Consígense métodos más xenerales tantu de fontes comerciales (como “FrameSearch”, distribuyíu como parte del paquete Accelrys GCG), como de software de códigu abiertu (como Genewise).

El métodu de programación dinámica garantiza atopar una alliniadura óptimo dada una función de puntuación en particular; sicasí, identificar una bona función de puntuación ye, usualmente, más una cuestión empírica que teórica. A pesar de que la programación dinámica ye estensible a más de dos secuencies, ye prohibitivamente lenta pa un altu númberu de secuencies desaxeradamente llargues.

Métodos de pallabra corta

Los métodos de pallabra curtia, tamién conocíos como métodos de k-tuplas, son métodos heurísticos que nun garanticen atopar una solución d'alliniadura óptima, pero son significativamente más eficientes que la programación dinámica. Estos métodos son especialmente útiles en busques sobre bases de datos a gran escala, onde s'asume qu'una llarga proporción de les secuencies candidates nun van tener coincidencies significatives con secuenciar problema. Los métodos de pallabra curtia son más conocíos pola so implementación nes ferramientes de busca en bases de datos FASTA y la familia BLAST.^[4] Estos métodos identifiquen en secuenciar problema una serie de subsecuencias curties que nun s'asolapen (“pallabres”), y que s'oldeen contra les secuencies de la base de datos. Les posiciones relatives de la pallabra nos dos secuencies a comparar restar pa llograr un valor de desplazamientu; va manifestase asina una rexón d'alliniadura si delles pallabres distintes producen el mesmu desplazamientu. Namái si esta rexón ye detectada, estos métodos van aplicar criterios d'alliniadura más sensibles. D'esta forma esaníciense munches comparances innecesaries ente secuencies de semeyanza inapreciable.

Nel métodu FASTA, l'usuariu define un valor “k” pa definir el llargor de la pallabra cola cual buscar na base de datos. El métodu ye más lentu, pero más sensible, pa valores baxos de “k”, que tamién son preferibles pa busques qu'impliquen una secuencia problema bien curtia. La familia BLAST de métodos de busca apurre dellos algoritmos optimizaos pa tipos particulares de problemes, tales como la busca de coincidencies ente secuencies escasamente rellacionaes. BLAST foi desenvueltu p'apurrir una alternativa más rápida a FASTA ensin sacrificar demasiada precisión. Como FASTA, BLAST utiliza una pallabra de busca de llargor “k”, pero namái evalúa les coincidencies más significatives de les pallabres, en llugar de cada coincidencia como fai FASTA. La mayoría de les implementaciones de BLAST usen un llargor de pallabra fita por defectu que s'optimiza pal problema y el tipu de base de datos, y que se camuda namái so circunstancies específiques tales como busques con secuencies problema repetitives o bien curties. Pueden atopase implementaciones al traviés de dellos portales web, como EMBL FASTA y NCBI BLAST.

Programación dinámica

La téunica de programación dinámica ye teóricamente aplicable a cualquier númberu de secuencies; sicasí, y yá que ye computacionalmente costosa tantu en tiempu como en memoria, raramente usar na so forma más básica pa más de trés o cuatro secuencies. Esti métodu rique la construcción d'un equivalente n-dimensional a la matriz formada por dos secuencies, onde “n” ye'l númberu de secuencies problema. La programación dinámica estándar úsase primero en tolos axugamientos ente secuenciar problema, polo que l'espaciu d'alliniadura” rellénase considerando posibles coincidencies o buecos nes posiciones entemedies, construyendo, finalmente y n'esencia, una alliniadura ente cada alliniadura de dos secuencies. Anque esta téunica ye computacionalmente costosa, la so garantía d'una solución global óptima ye útil en casos onde namái unes cuantes secuencies precisen ser alliniaes con precisión. Un métodu p'amenorgar les demandes computacionales de programación dinámica, que depende de la función oxetivu “suma de pares”, foi implementáu nel paquete de software MSA.^[6]

Métodos progresivos

Los métodu progresivos, xerárquicos, o por árbol, xeneren una alliniadura múltiple de secuencies alliniando primero les secuencies más similares, pa dir añadiendo socesivamente a l'alliniadura secuencies o grupos menos rellacionaos, hasta que'l conxuntu problema completu foi incorporáu a la solución. L'árbol inicial describiendo'l parentescu de les secuencies basar en comparances d'axugamientos que podríen incluyir métodos d'axugamientu heurísticu p'alliniadures similares a FASTA. Los resultaos de l'alliniadura progresiva dependen de la eleición de les secuencies “más rellacionaes”, polo que pueden ser sensibles a imprecisiones nes alliniadures d'axugamientos iniciales. La mayoría de los métodos progresivos d'alliniadura múltiple de secuencies sopesen adicionalmente les secuencies nel conxuntu problema d'alcuerdu al so parentescu, lo qu'amenorga la probabilidá d'efeutuar una probe eleición de les secuencies iniciales y asina s'ameyora la precisión de l'alliniadura.

Un bon númberu de variaciones de la implementación progresiva de Clustal^[7][8][9] utilizar p'alliniadures múltiples de secuencies, construcción d'árboles filoxenéticos, y como entrada pa la predicción d'estructura de proteínes. Una variante del métodu progresivu más lenta pero más precisa conozse como “T-Coffee” (Tree-based Consistency Objective Function For alignment Evaluation),^[10] de la que pueden atopase implementaciones en ClustalW y T-Coffee.

Métodos iterativos

Los métodos iterativos intenten ameyorar el puntu débil de los métodos progresivos: la so fuerte dependencia de la precisión de les alliniadures de los axugamientos iniciales. Los métodos iterativos optimicen una función oxetivu basada nun métodu escoyíu de puntuación d'alliniadura por aciu la asignación d'una alliniadura global inicial y el posterior realineamiento de subconxuntos de secuencies. Los subconxuntos realineados son entós alliniaos consigo mesmos pa producir la siguiente iteración d'alliniadura múltiple de secuencies. Atópense baxu analís delles formes de seleición de los subgrupos de secuencies y de la función oxetivu.^[11]

Descubrimientu de motivos

Pal descubrimientu de motivos, o analises de perfiles, constrúyense alliniadures múltiples globales de secuencies qu'intenten alliniar secuencies motivu curties calteníes ente les secuencies del conxuntu problema. Faise, usualmente, construyendo primero una alliniadura múltiple de secuencies global, tres el cual les rexones altamente calteníes identifíquense y utilícense pa construyir un conxuntu de matrices de perfil (tamién denominaes matrices ponderaes o matrices de pesos). La matriz del perfil de cada rexón caltenida dispónse como una matriz de puntuación, pero les sos cifres de frecuencia pa cada aminoácidu o nucleótido en cada posición derivar de la distribución de los calteres de la rexón caltenida, en llugar d'una distribución empírica más xeneral. Les matrices de perfil usar pa buscar escurrimientos del motivu que caractericen n'otres secuencies. Nos casos nos que'l conxuntu de datos orixinal contenga un pequeñu númberu de secuencies, o namái secuencies bien rellacionaes, añader pseudocontadores pa normalizar les distribuciones de calteres representaes nel motivu.

Téuniques inspiraes poles ciencies de la computación

Una variedá d'algoritmos xenerales d'optimización usaos comúnmente en ciencies de la computación aplicáronse tamién al problema de l'alliniadura de secuencies. Los modelos ocultos de Márkov utilizáronse pa producir rexistros de probabilidaes pa una familia de posibles alliniadures múltiples de secuencies sobre un conxuntu problema dau. Anque los primeros métodos basaos nestos modelos yeren de rendimientu pocu brillante, aplicaciones posteriores atopar especialmente efeutivos pa detectar secuencies remotamente rellacionaes, yá que son menos susceptibles al ruiu creáu por sustituciones conservativas o semiconservativas.^[12] Los algoritmos xenéticos y el simulated annealing usáronse pa optimizar les puntuaciones d'alliniadures múltiples de secuencies, valorándolos por aciu una función de puntuación como la del métodu de suma de pares.

DALI

El métodu DALI (del inglés, Distance matrix ALIgnment, alliniadura de matriz de distancies), ye un métodu fragmentariu pa construyir alliniadures estructurales basaos en contautar patrones de semeyanza ente socesivos hexapéptidos en secuenciar problema.^[15] Puede xenerar axugamientos o alliniadures múltiples, ya identificar los vecinos estructurales d'una secuencia problema nel Protein Data Bank (PDB). Usóse pa construyir la base de datos d'alliniadures estructurales FSSP (del inglés Families of Structurally Similar Proteins, families de proteínes estructuralmente similares). Puede aportase a un servidor web de DALI en EBI DALI , y la FSSP alcontrar nel Enllaz rotu|1=base de datos DALI |2=http://ekhidna.biocenter.helsinki.fi/dali/start |bot=InternetArchiveBot }}.

SSAP

SSAP (del inglés Sequential Structure Alignment Program, programa d'alliniadura d'estructura secuencial) ye un métodu d'alliniadura estructural basáu en programación dinámica qu'usa vectores “átomo a átomu” nel espaciu de la estructura como puntos a comparar. Estendióse dende la so descripción orixinal pa incluyir tanto alliniadures múltiples como axugamientos,^[16] y usóse na construcción del CATH (del inglés Class, Architecture, Topology, Homology; clase, arquiteutura, topoloxía, homoloxía), base de datos xerárquica de clasificación de plegamientos de proteínes.^[17] La base de datos CATH puede aportase na Clasificación d'Estructura de Proteínes CATH.

Estensión combinatoria

El métodu d'estensión combinatoria p'alliniadura estructural xenera una alliniadura estructural de pares usando xeometría local p'alliniar fragmentos curtios de los dos proteínes a analizar, y xuntar entós estos fragmentos nuna alliniadura mayor.^[18] Basáu en midíes tales como la raigañu del error cuadrático mediu en superposición de proteínes como sólidos ríxidos, distancies ente residuos, estructura secundaria local, y carauterístiques medioambientales circundantes tales como la hidrofobicidad de los residuos vecines, xenérense alliniadures locales llamaos “pares de fragmentos alliniaos” que s'usen pa construyir una matriz de semeyanza representando toles alliniadures estructurales posibles dientro d'un criteriu de corte predefinido. Trázase, entós, una trayeutoria dende un estáu de la estructura d'una proteína a otru al traviés de la matriz, estendiendo la creciente alliniadura un fragmentu cada vez. La trayeutoria óptima define l'alliniadura por estensión combinatoria. Un servidor web qu'implementa'l métodu y apurre una base de datos d'axugamientos d'estructura nel Protein Data Bank alcontrar nel sitiu de Combinatorial Extension.

Funciones de puntuación

Pa producir bones alliniadures ye importante la eleición d'una función de puntuación que reflexe observaciones biolóxiques o estadístiques sobre secuencies conocíes. Les secuencies de proteínes son alliniaes usando frecuentemente matrices de sustitución que reflexen les probabilidaes de particulares sustituciones calter per calter. Una serie de matrices denominaes matrices PAM (del inglés Point Accepted Mutation, mutación puntual aceptada, orixinalmente definíes por Margaret Dayhoff, polo que dacuando se denominen matrices Dayhoff) codifican explícitamente los aproximamientos evolutivos considerando les frecuencies y probabilidaes de mutaciones particulares d'aminoácidos. Otra serie común de matrices de puntuación, conocíes como BLOSUM (del inglés Blocks Substitution Matrix, matriz de sustitución de bloques), codifica probabilidaes de sustitución derivaes empíricamente. Utilícense variantes de dambos tipos de matrices pa detectar secuencies con distintos niveles de diverxencia, dexando asina a los usuarios de BLAST o FASTA acutar les sos busques a coincidencies más cercanamente rellacionaes, o estendeles pa detectar secuencies más diverxentes. Les penalizaciones por gaps representen la introducción de buecos (nel modelu evolutivu, una mutación por insertamientu o borráu) en secuencies tantu de nucleótidos como de proteínes, y estos valores de penalización, poro, tendríen de ser proporcionales a la frecuencia esperada de tales mutaciones. La calidá de les alliniadures producíes depende, arriendes d'ello, de la calidá de la función de puntuación.

Puede resultar bien útil ya instructivu intentar la mesma alliniadura distintes vegaes con distintes eleiciones de matrices de puntuación y/o distintos valores de penalización por buecos, y comparar los resultaos. Les rexones onde la solución seya pocu consistente, o nun seya única, pueden ser identificaes de cutiu reparando qué rexones de l'alliniadura son robustes a variaciones nos parámetros d'alliniación.