Gdfhxd

Introducción a los algoritmos de biología computacional

Técnicas Avanzadas de Programación - Javier Campos

393

Introducción a la biología computacional • El plan:
– Algoritmos de reconocimiento de patrones:
• Knuth-Morris-Pratt • Boyer-Moore

– Árboles de sufijos – Primeras aplicaciones de los árboles de sufijos

Técnicas Avanzadas de Programación - Javier Campos

394Reconocimiento de patrones • El problema de la subcadena o reconocimiento exacto de un patrón:
– Dados una cadena madre de n caracteres S = ‘s1 s2 … sn’ y un patrón de m caracteres (nm) P = ‘p1 p2 … pm’ se quiere saber si P es una subcadena de S y, en caso afirmativo, en qué posición(es) de S se encuentra. – Instrucción crítica para medir la eficiencia de las soluciones:
• número de comparacionesentre pares de caracteres
Técnicas Avanzadas de Programación - Javier Campos 395

Reconocimiento de patrones • Importancia del problema:
– Imprescindible en gran número de aplicaciones:
• • • • • • • • • • • • Procesadores de textos, utilidades como el grep de unix, programas de recuperación de información textual, programas de búsqueda en catálogos de bibliotecas, buscadores de internet,lectores de news en internet, bibliotecas digitales, revistas electrónicas, directorios telefónicos, enciclopedias electrónicas, búsquedas en bases de datos de secuencias de ADN o ARN, …

– Problema bien resuelto en determinados casos pero…
Técnicas Avanzadas de Programación - Javier Campos 396

The anatomy of a genome (1)
• Genome = set of all DNA contained in a cell. • Formed by one or morelong stretches of DNA strung together into chromosomes. • Chromosomes are faithfully replicated by a cell when it divides. • The set of chromosomes in a cell contains the DNA necessary to synthesize the proteins and other molecules needed to survive, as well as much of the information necessary to finely regulate their synthesis
– Each protein is coded for by a specific gene, a stretch of DNAcontaining the information necessary for that purpose.

Formal Models in Bioinformatics –de Programación - Javier Campos Técnicas Avanzadas Javier Campos

397

The anatomy of a genome (2)
• DNA molecules consist of a chain of smaller molecules called nucleotides that are distinct from each other only in a chemical element called a base. For biochemical reasons, DNA sequences have an orientation– It is possible to distinguish a specific direction in which to read each chromosome or gene – The directions are often represented as the left and right end of the sequence

•

• • • •

A DNA sequence can be single-stranded or double-stranded. The double-stranded nature is caused by the pairing of bases (base pairs, bp). When it is double-stranded, the two strands have opposite directionand are complementary to one another. This complementarity means that for each A, C, G, T in one strand, there is a T, G, C, or A, respectively, in the other strand.

Formal Models in Bioinformatics –de Programación - Javier Campos Técnicas Avanzadas Javier Campos

398

The anatomy of a genome (3)
• • • Chromosomes are double-stranded (“double helix”) Information about a gene can becontained in either strand. This pairing introduces a complete redundancy in the encoding
– allows the cell to reconstitute the entire genome from just one strand (enables faithful replication) – for simple convenience, we usually just write out the single strand of DNA sequence we are interested in from left to right

• • •

The letters of the DNA alphabet are variously called nucleotides (nt),bases, or base pairs (bp) for double stranded DNA. The length of a DNA sequence can be measured in bases, or in kilobases (1000 bp or Kb) or megabases (1000000 bp or Mb). The genomes present in different organisms range in size from kilobases to megabases.

Formal Models in Bioinformatics –de Programación - Javier Campos Técnicas Avanzadas Javier Campos

399

Reconocimiento de patrones...