Pregunta n 1: La vecindad d Vecinos(Patrn, d) es el conjunto de todos los k-mers cuya distancia Hamming al Patrn no supera d. Generar la vecindad d de una cadena Encontrar todos los vecinos de un patrn. Dados: Una cadena de ADN Patrn y un nmero entero d. Devuelve: La coleccin de cadenas Vecinos(Patrn, d). Conjunto de datos de muestra ACG 1 Salida de muestra CCG TCG GCG AAG ATG AGG ACA ACC ACT ACG Pregunta n 2: Decimos que un Patrn k-mer aparece como una subcadena del Texto con a lo sumo d desajustes si hay alguna subcadena k-mer Patrn' del Texto que tenga d o menos desajustes con el Patrn, es decir, HammingDistance(Patrn, Patrn') d. Nuestra observacin de que una caja DnaA puede aparecer con ligeras variaciones nos lleva a la siguiente generalizacin del Problema de Coincidencia de Patrones. Problema de coincidencia de patrones aproximados Encontrar todas las ocurrencias aproximadas de un patrn en una cadena. Dados: Las cadenas Patrn y Texto junto con un nmero entero d. Devuelve: Todas las posiciones iniciales en las que el Patrn aparece como subcadena del Texto con un mximo de d desajustes. Conjunto de datos de muestra ATTCTGGA CGCCCGAATCCAACGCATTCCCATATTTCGGACCACTGGCCTCCACGGTACGACGTCAAATGCCTAGCGCTTGTGTCTCCTACGCTCC 3 Muestra de salida 6 7 26 27 78 Pregunta n 3: Hemos definido un desajuste en "Calcular la distancia de Hamming entre dos cadenas". Ahora generalizamos "Encontrar las palabras ms frecuentes en una cadena" para incorporar tambin las discordancias. Dadas las cadenas Texto y Patrn, as como un nmero entero d, definimos Countd(Texto, Patrn) como el nmero total de ocurrencias del Patrn en el Texto con un mximo de d desajustes. Por ejemplo, Count1(AACAAGCTGATAAACATTTAAAGAG, AAAAA) = 4 porque AAAAA aparece cuatro veces en esta cadena con un mximo de un desajuste: AACAA, ATAAA, AAACA y AAAGA. Ntese que dos de estas ocurrencias se superponen. Un k-mero ms frecuente con hasta d desajustes en el Texto es simplemente una cadena Patrn que maximiza Countd(Texto, Patrn) entre todos los k-meros. Tenga en cuenta que no es necesario que Patter aparezca realmente como una subcadena de Texto; por ejemplo, AAAAA es el 5-mero ms frecuente con 1 desajuste en AACAAGCTGATAAACATTTAAAGAG, aunque AAAAA no aparezca exactamente en esta cadena. Tenlo en cuenta al resolver el siguiente problema. Problema de palabras frecuentes con desajustes Encontrar los k-mers ms frecuentes con desajustes en una cadena. Dado: Una cadena de texto, as como los enteros k y d. Devuelve: Todos los k-mers ms frecuentes con hasta d desajustes en el Texto. Conjunto de datos de muestra ACGTTGCATGTCGCATGATGCAGAGCT 4 1 Muestra de salida GATG ATGC ATGT Pregunta n 4 Ahora ampliamos "Encontrar las palabras ms frecuentes con desajustes en una cadena" para encontrar palabras frecuentes tanto con desajustes como con complementos inversos. Recordemos que Patrn se refiere al complemento inverso de Patrn. Palabras frecuentes con desajustes y complementos inversos Problema Encuentre los k-mers ms frecuentes (con desajustes y complementos inversos) en una cadena de ADN. Dado: Una cadena de ADN Texto as como los enteros k y d. Devuelve: Todos los k-mers Patrn que maximizan la suma Countd(Texto, Patrn) + Countd(Texto, Patrn) sobre todos los k-mers posibles. Conjunto de datos de muestra ACGTTGCATGTCGCATGATGAGCT 4 1 Salida de muestra ATGT ACAT