{"id":39376,"date":"2006-09-01T13:22:00","date_gmt":"2006-09-01T13:22:00","guid":{"rendered":"http:\/\/weblogs.madrimasd.org\/\/bioinformatica\/archive\/2006\/09\/01\/39376.aspx"},"modified":"2006-09-01T13:22:00","modified_gmt":"2006-09-01T13:22:00","slug":"algoritmos-de-alineamiento-de-secuencias","status":"publish","type":"post","link":"https:\/\/www.madrimasd.org\/blogs\/bioinformatica\/2006\/09\/01\/39376","title":{"rendered":"Algoritmos de alineamiento de secuencias"},"content":{"rendered":"

Siguiendo el hilo del mensaje anterior, Manuel, el estudiante de Biolog\u00eda interesado en Bioinform\u00e1tica me pregunt\u00f3 en un correo de vuelta si los algoritmos de alineamiento de secuencias que se usan hoy en d\u00eda funcionan bien. No creo ser la persona con m\u00e1s experiencia en el tema para responder, pero aqu\u00ed va:<\/p>\n

    Los algoritmos de hoy en d\u00eda funcionan bastante bien para encontrar secuencias similares que puedan ser hom\u00f3logas de la usada como entrada. Se puede decir que los resultados son cre\u00edbles hasta un porcentaje del 30% de similitud, siempre y cuando la secuencia tenga una longitud m\u00ednima aproximada de 30 res\u00edduos (ya sean amino\u00e1cidos o nucle\u00f3tidos). Claro est\u00e1, el funcionamiento de cualquier algoritmo de alineamiento de secuencias depende mucho de la calidad de la base de datos de secuencias que uses, y de tu conocimiento sobre lo que buscas para afinar en los par\u00e1metros de ejecuci\u00f3n.<\/p>\n

    Los algoritmos de alineamiento de secuencias de hoy en d\u00eda son un est\u00e1ndar de facto en la bioinform\u00e1tica, y casi siempre la base para m\u00e9todos m\u00e1s complejos. Uno de los primeros est\u00e1ndares fue, ya hace bastantes a\u00f1os, el algoritmo de Smith&Waterman<\/a>, que est\u00e1 basado en una estrategia de comparaci\u00f3n y b\u00fasqueda exhaustiva de secuencias usando programaci\u00f3n din\u00e1mica. A medida que fue creciendo el tama\u00f1o de las bases de datos se hizo inviable usar esta estrategia (es un algoritmo O(n2<\/sup>) en espacio y tiempo), y se migr\u00f3 a una en la que, aunque no se encontrara siempre el mejor resultado, evitara realizar buena parte de las comparaciones.<\/p>\n

    De ah\u00ed naci\u00f3 el algoritmo FASTA, muy usado todav\u00eda hoy en d\u00eda en algunas partes. La comunidad bioinform\u00e1tica termin\u00f3 rechazando este algoritmo porque, a pesar de funcionar muy bien, no estaba basado en conceptos biol\u00f3gicos. Esto sucedi\u00f3 cuando apareci\u00f3 el algoritmo Blast, que evolucion\u00f3 posteriormente a Gapped Blast, que es el est\u00e1ndar de facto actual.<\/p>\n

    La implementaci\u00f3n gratuita m\u00e1s aceptada, y que suele tomarse como referencia es NCBI Blast<\/a>. Se ha hecho tan indispensable desde su aparici\u00f3n hace casi 10 a\u00f1os que existen diversas implementaciones paralelizadas. Personalmente he tenido el placer de usar un par de implementaciones en hardware, que aceleran las b\u00fasquedas de manera ‘brutal’.<\/p>\n

    Existen m\u00e1s algoritmos de alineamiento de secuencias posteriores a Blast, y que tienen su propio nicho. Algunos de ellos son PSI-Blast<\/a>, ssearch (b\u00e1sicamente una implementaci\u00f3n del Smith&Waterman) y BLAT<\/a>. El primero est\u00e1 especializado en b\u00fasquedas de hom\u00f3logos remotos, el segundo es m\u00e1s ‘sensitivo’, a costa de m\u00e1s tiempo de ejecuci\u00f3n, mientras que el tercero se usa para realizar de forma eficiente comparaciones masivas de genoma contra genoma y cromosoma contra cromosoma.<\/p>\n

    Seguro que hay m\u00e1s de un lector con conocimientos m\u00e1s profundos de este tema, as\u00ed que \u00a1bienvenidos seais!<\/p>\n

Enlaces<\/u>:<\/p>\n