Diseño y análisis de nuevos algoritmos en bioinformática (2002)
Dos metas importantes en la Biología Molecular Computacional son las búsquedas de regularidades en secuencias nucleicas o de la proteína, y encontrar las características que son comunes a un conjunto de tales secuencias. En todos los casos, la conservación de un patrón no es imperativo. La posibilidad de errores (substituciones, cancelaciones o inserciones) debe por lo tanto ser considerado. La flexibilidad se puede también introducir, alternativa o simultáneamente, permitiendo que los modelos sean escritos sobre un alfabeto integrado por los subconjuntos del alfabeto de los nucleótidos (ADN/ARN) o de los aminoácidos (proteínas), incluyendo el comodín (wild card). Las regularidades en una secuencia pueden venir bajo muchas fisonomías. Pueden corresponder a las repeticiones aproximadas dispersadas aleatoriamente a lo largo de la secuencia, o a las repeticiones que ocurren en una manera periódica o aproximadamente periódica, O bien a tandas de arreglos (tandem arrays). Para muchos de los problemas en biología molecular, en particular el estudio de la expresión y regulación del gen es importante poder deducir lo que se ha llamado "patrones estructurados". En este proyecto, dos algoritmos de naturaleza combinatoria se han propuesto como soluciones al problema de la búsqueda de cuadrados (squares) y búsquedas de cadenas evolutivas. En [1] se presenta un algoritmo capaz de encontrar “squars” en un tiempo O(n2). En [2] se trata el problema de evolución. Una cadena evolutiva es la deformación de una sub-cadena original (denominada la raíz). Esta deformación es lo que comúnmente se conoce con el nombre de una mutación. Una mutación ocurre cuando una base desaparece, es insertada o es simplemente sustituida. Aunque este articulo muestra su aplicación directa en la música es posible trasladar este concepto directamente a la Biología. Es claro que el conocimiento alcanzado con este estudio puede ser la base para posibles publicaciones directamente en la Biocomputación.