advertisement

Bioinformatics Biostatistics with dynamic programming and sequence alignment

44 %
56 %
advertisement
Information about Bioinformatics Biostatistics with dynamic programming and sequence...
Technology

Published on March 7, 2014

Author: vlopezlo

Source: slideshare.net

Description

Bioinformatics Biostatistics with dynamic programming and sequence alignment. Data bases in biology. Optimization, algorithms and methods
advertisement

Victoria López, vlopezlo@ucm.es, 1 Despacho 309 Facultad de Informática

1. 2. 3. 4. 5. 6. 7. Introducción a la Bioinformática Estructura de proteínas y ácidos nucleicos Análisis de Secuencias Bases de datos en Biología Análisis de datos: técnicas de agrupamiento Minería de datos en Bioinformática Lenguaje R* y aplicaciones a Bioinformática 2

– Compilador de R : http://cran.r-project.org/ – Libros: http://www.r-project.org/ • Manuals  contributed documentation: – “Applied Statistics for Bioinformatics Using R” by Wim Krijnen – “Statistics Using R with Biological Examples” by Kim Seefeld and Ernst Linder – “Practical Regression and Anova using R” by Julian Faraway – “R and Data Mining: Examples and Case Studies” by Yanchang Zhao 3

• Exposiciones teóricas basadas en la bibliografía y en artículos. Sesiones prácticas con R. • Presentación de los trabajos por parte de los alumnos: exposiciones individuales del tema desarrollado a partir de los documentos proporcionados en el Campus Virtual y vía Web (documentación utilizada en clase, presentaciones y artículos). Criterios de evaluación: • Asistencia y participación en las discusiones (30%), trabajo práctico individual y exposición (70%) 4

07/03/2014 Introducción a la Bioinformática 5

We are drowning in information and starved for knowledge John Naisbitt Who on efficient work is bent, Must choose the fittest instrument. Goehthe (Fausto) 07/03/2014 Introducción a la Bioinformática 6

• • • • • • • 07/03/2014 Introducción: La explosión de información Sobre información biológica Pero,… qué es la bioinformática? Los grandes bloques temáticos de la BIF Los grandes centros y bancos de datos Un poco de práctica Referencias Introducción a la Bioinformática 7

• El fin del siglo XX ha visto una explosión de información provinente de los seres vivos, especialmente en biología molecular – Secuenciación de genomas – Secuencia y estructura de proteínas – Estudios sobre la expresión simultánea de muchos genes bajo muchas condiciones diferentes. 07/03/2014 Introducción a la Bioinformática 8

El crecimiento explosivo de datos Hace ... Nucleótidos 26 años (1982) Antes 680338 pb (GenBank) Ahora > Miles de millones Proteínas 26 años 1500 300.000 DNA continuo 16 años 73 kb > 270 Mbases SNPs 16 años centenares 11 millones Genomas 11 años 0 organismos 1282 Organismos (mediados 2010) Expresión 07/03/2014 10 años Limitado pocos genes Introducción a la Bioinformática Miles de estudios con miles de genes 9

(1982-2000) 07/03/2014 Introducción a la Bioinformática 10

07/03/2014 Introducción a la Bioinformática 11

• La información biológica se encuentra – codificada en los genes y – se expresa a partir / mediante los genes • Esta idea se refleja en el Dogma Central de la Biologia Molecular 07/03/2014 Introducción a la Bioinformática 12

07/03/2014 Introducción a la Bioinformática 13

• La biología se enfrenta con el problema de la decodificación del lenguaje biológico – Como se codifica la información en los genes? – Como (cuando, ...) se traduce esta información? • Ej. Splicing alternativo – Qué determina la estructura de las proteínas? – Como se determina la función de las proteínas • La bioinformática sirve para estudiar como se procesa toda esta información biológica 07/03/2014 Introducción a la Bioinformática 14

07/03/2014 Introducción a la Bioinformática 15

• Los ácidos nucleicos (AN) contienen la información para generar los organismos: DNA  RNA  PROTEINAS  Función • Las proteínas se forman con aminoácidos (AA) unidos en secuencias lineales • Las instrucciones para definir la secuencia de AA están codificadas en los AN por grupos de tres nucleótidos, en un código genético redundante 07/03/2014 Introducción a la Bioinformática 16

07/03/2014 Introducción a la Bioinformática 17

• Las secuencias biológicas se organizan en grupos con un significado, en general desconocido para nosotros • Podemos distinguir una jerarquía (niveles de organización) que podemos comparar con – Frases (las proteínas) – Palabras (motivos o configuraciones) – Letras (Los AA o los nucleótidos) 07/03/2014 Introducción a la Bioinformática 18

• Las secuencias, establecidas experimentalmente se representan como cadenas de un alfabeto y se comparan – Regiones comunes asocian las palabras a propiedades comunes de las moléculas – Regiones diferentes revelan palabras con un sentido asociado a propiedades que diferencian a las moléculas – Muchas regiones no contienen información 07/03/2014 Introducción a la Bioinformática 19

• Nace a partir del – desarrollo de nuevas tecnologías y de – su aplicación para la generación de grandes cantidades de datos. • La disciplina científica que engloba todos los aspectos de la adquisición, procesamiento, distribución, análisis, interpretación e integración de la información biológica 07/03/2014 Introducción a la Bioinformática 20

Chemistry Biology Molecular biology Mathematics Statistics Bioinformatics Computer Science Informatics Medicine Physics 07/03/2014 Introducción a la Bioinformática 21

07/03/2014 Introducción a la Bioinformática 22

• Computational biology applies the techniques of computer science, applied mathematics and statistics to address biological problems. • Bioinformatics is the application of information technology to the field of molecular biology. 07/03/2014 Introducción a la Bioinformática 23

The future of genomics rests on the foundation of the Human Genome Project 07/03/2014 Introducción a la Bioinformática 24

07/03/2014 Introducción a la Bioinformática 25

• Organización de la información – Bases y bancos de datos – Algoritmos y herramientas de explotación • Análisis e interpretación de resultados experimentales – Secuenciación y análisis de genomas – Genómica Comparatíva – Transcriptómica y expresión génica – Proteómica, redes de interacción PPI • Modelos de Sistemas Biológicos 07/03/2014 Introducción a la Bioinformática 26

07/03/2014 Introducción a la Bioinformática 27

AGAGTTCTGCTC G AG G GTTATG C G C G 07/03/2014 Introducción a la Bioinformática 28

07/03/2014 Introducción a la Bioinformática 29

07/03/2014 Introducción a la Bioinformática 30 30

Datos Recursos y herramientas bioinformáticos Conocimiento • Como quiera que se defina, desde donde quiera que se mire, el papel de la Bioinformática ha sido, es y será crucial para el avance de la Biología y la Medicina del siglo XXI 07/03/2014 Introducción a la Bioinformática 31

• Debe tener “sólidos conocimientos” en – Alguna disciplina biológica • Bioquímica, Genética,… – Entornos de desarrollo informáticos • SO [Linux], Lenguajes[Perl, Java, R], Bases de datos [SQL], Desarrollo web [PHP, ASP, Ajax…] – Alguna disciplina cuantitativa • [Matemáticas, Estadística, Física] Al menos dos de las tres anteriores!! 07/03/2014 Introducción a la Bioinformática 32

• Gestión de la información – Implementación y explotación de bases de dados locales o en internet. – Instalación, mantenimiento de servidores web. • Desarrollo de aplicaciones – Elaboración de programas locales o web, • Explotación y análisis de datos – Microarrays, datos de alto rendimiento 07/03/2014 Introducción a la Bioinformática 33

• Centros Especializados – EBI, NCBI, EMBL. – INB / Plataforma Bioinformatica de la UAB. • Servicios Bioinformáticos de centros de investigación, – UEB, UBB, BU • Universidades, • Laboratorios Farmacéuticos, • … 07/03/2014 Introducción a la Bioinformática 34

• Usualmente, aunque no necesariamente la BIF tiene vocación “universal”, de acceder al máximo de usuarios: – Suele buscarse soluciones WEB – Suele basarse en proyectos [más o menos] open source de distribución libre. • Esto no es del todo general – Por ejemplo Ingenuity Pathway Analysis no es gratis pero es bueno. 07/03/2014 Introducción a la Bioinformática 35

• Existen multitud de recursos gratuitos – 2can en el EBI – Tutoriales del NCBI – Cursos “locales” • Introducción a la Bioinformatica (A. Sanchez UEB/UB) • Invitacio a la Bioinformatica (Plataforma BIF UAB) • Una gran variedad de libros sobre el tema – List of books on bioinformatics • Revistas y sociedades científicas – Bioinformatics, Briefings in Bioinformatics – International Society for Computational Biology 07/03/2014 Introducción a la Bioinformática 36

07/03/2014 Introducción a la Bioinformática 37

• Buena parte del trabajo en bioinformática consiste en la construcción y/o explotación de bases de datos de información biológica • Se usan, por ejemplo para: – Añadir o buscar información (“anotaciones”) – Buscar similitudes o patrones – Hacer predicciones • De estructura o función en proteínas • De genes en genomas 07/03/2014 Introducción a la Bioinformática 38

• La WWW ha revolucionado la provisión de servicios en bioinformática • Muchas cosas pueden hacerse a través de internet sin que sean necesarias copias locales de las bases de datos o el software para explotarlas • A pesar de esta globalización existen organizaciones que centralizan los recursos 07/03/2014 Introducción a la Bioinformática 39

• Centros importantes a nivel mundial – EMBL / EBI (www.embl.org / www.ebi.ac.uk ) – NCBI ( www.ncbi.nlm.nih.gov ) – DDBJ ( www.ddbj.nig.ac.jp ) • Bases de datos biológicas – – – – 07/03/2014 EMBL DNA sequence database SWISSPROT i TREMBL PIR, PDB Catálogo de bases de datos biológicas www.infobiogen.fr/services/dbcat Introducción a la Bioinformática 40

07/03/2014 Introducción a la Bioinformática 41

1. 2. 3. Clasificación de un hongo, comparando una secuencia suya con las de una base de datos para determinar si las hay similares Visualización de estructuras moleculares en tres dimensiones Introducción al análisis de secuencias 07/03/2014 Introducción a la Bioinformática 42

• Unos investigadores han detectado una infección fúngica en un cultivo agrario. • En caso de duda en la identificación directa (crecimiento lento del hongo, características morfológicas similares entre varias especies, etc.) se puede plantear la alternativa siguiente: – Secuenciar un fragmento del ADN del hongo – Buscar en bases de datos moleculares intentando encontrar la misma secuencia o una lo más similar posible (“DB homology search”) 07/03/2014 Introducción a la Bioinformática 43

• Obtenemos la secuencia siguiente • gtttacgctctacaaccctttgtgaacatacctacaactgtt gcttcggcgggtagggtctccgcgaccctcccggcctcccgc ctccgggcgggtcggcgcccgccggaggataaccaaactctg atttaacgacgtttcttctgagtggtacaagcaaataatcaa aacttttaacaaccggatctcttggttctggcatcgatgaag aacgcagcgaaatgcgataagtaatgtgaat 07/03/2014 Introducción a la Bioinformática 44

1. Vía internet accedemos al EBI: European Bioinformatics Institute 2. Aquí escogemos la opción “Tools” y 1. Seleccionamos Fasta3  2. Seleccionamos en DATABASES : Nucleic ACIDS , FUNGI 3. Enganchamos la secuencia y hacemos la consulta 3. Obtendremos un listado de especies ordenado de mayor a menor similitud 07/03/2014 Introducción a la Bioinformática 45

07/03/2014 Introducción a la Bioinformática 46

07/03/2014 Introducción a la Bioinformática 47

07/03/2014 Introducción a la Bioinformática 48

07/03/2014 Introducción a la Bioinformática 49

07/03/2014 Introducción a la Bioinformática 50

• • • • FASTA searches a protein or DNA sequence data bank version 3.3t09 May 18, 2001 Please cite: W.R. Pearson & D.J. Lipman PNAS (1988) 85:2444-2448 • • • • @:1-: 241 nt • • • • • 104701680 residues in 66478 sequences statistics extrapolated from 60000 to 61164 sequences Expectation_n fit: rho(ln(x))= -1.2290+/-0.000361; mu= 72.1313+/- 0.026 mean_var=907.6270+/-295.007, 0's: 68 Z-trim: 4246 B-trim: 15652 in 3/79 Lambda= 0.0426 • • • • • • • • • • • • • FASTA (3.39 May 2001) function [optimized, +5/-4 matrix (5:-4)] ktup: 6 join: 48, opt: 33, gap-pen: -16/ -4, width: 16 Scan time: 3.180 The best scores are: opt bits E(61164) EM_FUN:CGL301988 AJ301988.1 Colletotrichum glo (1484) [f] 1184 88 5.7e-17 EM_FUN:AF090855 AF090855.1 Colletotrichum gloe ( 500) [f] 1205 88 7.3e-17 EM_FUN:CGL301986 AJ301986.1 Colletotrichum glo (1484) [f] 1166 87 1.2e-16 EM_FUN:CGL301908 AJ301908.1 Colletotrichum glo (2868) [f] 1148 87 1.3e-16 EM_FUN:CGL301909 AJ301909.1 Colletotrichum glo (2868) [f] 1148 87 1.3e-16 EM_FUN:CGL301907 AJ301907.1 Colletotrichum glo (2867) [f] 1148 87 1.3e-16 EM_FUN:CGL301919 AJ301919.1 Colletotrichum glo (1171) [f] 1166 87 1.6e-16 EM_FUN:CGL301977 AJ301977.1 Colletotrichum glo (1876) [f] 1148 86 2e-16 EM_FUN:CFR301912 AJ301912.1 Colletotrichum fra (2870) [f] 1137 86 2.1e-16 07/03/2014 vs EMBL Fungi library searching /ebi/services/idata/v225/fastadb/em_fun library Introducción a la Bioinformática 51

• RASMOL es un programa para visualizar estructuras moleculares en tres dimensiones • Haciendo click aquí podéis acceder a una guía rápida del programa desde donde podréis descargarlo, instalarlo y ejecutarlo con facilidad 07/03/2014 Introducción a la Bioinformática 52

• Haciendo click aquí se accede al Bioinformatics Web Practical del servicio de Bioinformática de la Universidad de Manchester (UMBER) • El objetivo de este tutorial es – Dar un vistazo a algunos recursos bioinformáticos existentes en Internet – Adquirir una primera idea sobre que es el análisis de secuencias • A continuación podéis ver algunas de las pantallas que aparecerán 07/03/2014 Introducción a la Bioinformática 53

07/03/2014 Introducción a la Bioinformática 54

Traducción de la secuencia y búsqueda en OWL 07/03/2014 Introducción a la Bioinformática 55

La secuencia ha sido identificada 07/03/2014 Introducción a la Bioinformática 56

• En organismos vivos (in vivo) • En entornos o ambientes artificiales (in vitro) • Mediante chips de silicona con los que construir microprocesadors (in silicio) 57

2. Estructura de proteínas y ácidos nucleicos 58

• Proteínas presentes en la alimentación • Compuestas por aminoácidos (aa) – Moléculas orgánicas complejas hechas de carbono, hidrógeno, oxígeno, nitrógeno y sulfuro – C1200H4000O600N300S100 • Interesa estudiar propiedades de las proteínas • Para ello se buscan representaciones adecuadas de su estructura molecular • Las proteínas son „macromoléculas‟: de 100 a 500 aminoácidos. 59

60

61

• Los aminoácidos tienen tres representaciones diferentes: – Mediante su nombre (Glutamina, Tirosina, …) – Mediante un código de letra única (Q, Y,…) – Mediante un código de tres letras (Gln, Tyr,…), este último acordado por el IUPAC (International Union of Pure and Applied Chemistry) 62

• Propiedades básicas de las proteínas: – Un tipo de proteína contiene siempre exactamente el mismo número de aminoácidos (también denominados residuos) – Insulina=30glicerinas+44 alcalinas+5tirosinas+… – Los aminoácidos de un tipo de proteína están asociados como una cadena y además se puede conocer el orden exacto de su constitución de aminoácidos. – La primera proteína o secuencia de aminoácidos que se descubrió fue la insulina en 1951 por F. Sanger. Se trata de una cadena formada por 110 residuos. 63

• Nacimiento 13 de agosto de 1918 • Conocido por: • Su trabajo sobre la bioquímica de los ácidos nucleicos. • Su trabajo sobre la estructura de las proteínas, en especial de la insulina. • Sociedades: • Royal Society(1954) • Premios destacados • Premio Nobel de Química (1958). Premio Nobel de Química (1980). Orden del Imperio Británico(1963). Medalla Copley (1977). Orden de Mérito del Reino Unido(1986). Medalla Royal (1977) • Con este investigador y con el estudio de las secuencias moleculares la biología pasó de ser un soft science (frente a la física y a la química) a ser una ciencia fundamental. 64

• Años 60: ordenadores poco potentes, no se pueden ejecutar búsquedas ni realizar reconocimiento de secuencias con agilidad. • Las secuencias se analizan y se comparan manualmente, escribiéndolas en papel y pegándolas en paredes (pattern matching) • Con el estudio, la manipulación y el análisis de las secuencias de proteínas usando computadores se inicia la bioinformática. Hasta los 80 no se revela un avance significativo, pero desde esa fecha, el crecimiento es exponencial debido al avance de la tecnología y los procesadores en particular. 65

Las 20 moléculas de aminoácidos en las proteínas tienen cuerpos diferentes. La raíz o nivel superior es el código de un aminoácido de la tabla o código de una letra, mientras que sus hijos (hooks o ganchos) en el nivel siguiente son siempre de la forma NH2 y COOH, como se muestra en la Figura 1. Estos grupos de átomos se usan para formar los conocidos ‘peptidic bounds’ entre sucesivos residuos de la secuencia. 66

Los enlaces peptídicos o enlaces entre dos aminoácidos (enlace amina) son reacciones químicas entre el grupo amino (NH2) de un aminoácido y el grupo carboxilo (COOH) de otro aminoácido formándose un enlace covalente entre el átomo de carbono y el de nitrógeno: OC-NH con la pérdida de un grupo OH y un H para formar una molécula de agua. La cadena de aminoácidos sólo define la proteína pero no informa por sí misma de las características biológicas o propiedades de dicha proteína. Nos interesa conocer, por ejemplo, la habilidad de la proteína para digerir el azúcar, o para formar parte de un tejido muscular, etc. Estas propiedades vienen dadas por la forma tridimensional que la cadena adopta en su ambiente. 67

Estructuras 3D • Una molécula de proteína es una cadena de eslabones no flexibles, la estructura es rígida, compacta y bien limitada. • Su forma 3D depende de la secuencia y el comportamiento de algunos aminoácidos en determinados ambientes. • La primera estructura 3D de una proteína fue determinada en 1958 por Kendrew y Perutz. • Las proteínas con igual secuencia pueden plegarse en formas similares • Proteínas con estructuras similares pueden codificarse como secuencias similares de aminoácidos.

Estructuras 3D • La función de la proteína es una consecuencia directa de su estructura 3D, es decir, de su forma o shape. • Análisis de la proteína: Secuencia estructura  función • Bioinformática estructural: Representación gráfica de la proteína y su visualización 3D

John Cowdery Kendrew • Oxford, Inglaterra 1917 - Cambridge 1997 • Químico inglés galardonado con el Premio Nobel de Química del año 1962. • Adjunto de Max Perutz en el Laboratorio de Biología Molecular del Britain's Medical Research Council, • Colaboró con él en el estudio de la estructura de las proteínas de los glóbulos rojos, realizando investigaciones paralelas a las de Perutz sobre la proteína muscular denominada mioglobina. • Los diagramas de difracción de rayos X en las cadenas peptídicas que constituyen la molécula de la mioglobina y en la cual se habían fijado previamente átomos pesados de oro o mercurio, le permitieron dilucidar la estructura espacial de esta molécula en 1959. En 1962 compartió con Perutz el Premio Nobel de Química por estos trabajos.

Max Ferdinand Perutz • Viena, 19 de mayo de 1914 - Cambridge, 6 de febrero de 2002 • Fue un químico británico, de origen austríaco, galardonado con el Premio Nobel de Química del año 1962. • En 1953 descubrió que, incorporando un átomo pesado (oro o mercurio) a cada una de las moléculas de la red cristalina de la hemoglobina, se producían pequeñas modificaciones en su correspondiente posición, la interpretación del cual le permitió dar a conocer en 1960 el primer modelo tridimensional de la molécula de la hemoglobina. • En 1959 consiguió determinar la estructura molecular de la mioglobina, por la cual Perutz y Kendrew fueron galardonados con el Premio Nobel de Química de 1962.

Definición de proteína • Las proteínas son compuestos químicos formados por la combinación de veinte pequeñas moléculas denominadas aminoácidos (aa). Químicamente se componen sobretodo de carbono, hidrógeno, oxígeno y nitrógeno aunque también pueden presentar otros elementos (azufre, hierro, fósforo, zinc o cobre). Las proteínas pueden formarse únicamente por aa (holoproteínas) o contar con una parte no proteica (heteroproteínas) y participan en un elevado número de funciones en el organismo. • Montserrat Camiña Tato • Bióloga - Investigación Biomédica - Universidad de Santiago de Compostela

Bioinformática de la Proteína • Recuperación de secuencias de proteínas desde bases de datos en Internet. • Cálculo de la composición de aminoácidos, peso molecular, punto isoeléctrico y otros parámetros de la proteína. • Visualización de estructuras. • Búsqueda de proteínas con estructura similar a una secuencia dada • Clasificación de proteínas en familias. • Búsqueda del mejor alineamiento entre dos o más proteínas • Etc.

Análisis de las secuencias de ADN El ADN es otro tipo de macromolécula (ácido dexioribonucleico) parecida a la proteína. Su estructura es también una cadena, pero en esta caso presenta la forma de una doble hélice y cada enlace de la cadena es una pareja de nucleóticos de un grupo de 4 posibles, frente a los 20 aminoácidos en la proteína. En este sentido la estructura del ADN es más sencilla que la de la proteína. Por eso los estudios sobre el ADN han sido mucho más rápidos.

Tabla de la codificación de los nucleótidos

Estructura del ADN • Hasta los años 70 no pudo determinarse la secuencia de moléculas del ADN ni su alfabeto de 4 nucleótidos. • Estos 4 elementos tienen distintos cuerpos pero el mismo par de ganchos (hooks): 5‟D y 3‟OH. Se asocian de forma similar a como ocurría con la estructura de la proteína.

AND: Doble Hélice • Una secuencia de ADN siempre se define como la sucesión de sus nucleótidos desde el 5‟ hasta el 3‟. • En 1953 se descubrió la forma de doble hélice de la molécula del ADN • Consiste en dos cadenas complementarias respecto a las moléculas enfrentadas. • Los emparejamientos A-T, G-C, etc., se realizan de forma biyectiva uno a uno y con relación recíproca. • A partir de una hebra, se puede deducir la otra complementaria directamente.

AND: Doble Hélice •La mayoría de los programas de Data Mining, como por ejemplo BLAST, tienen en cuenta las dos cadenas pero algunos programas solo analizan la secuencia que dada como cadena única. •Dependiendo del tipo de estudio será importante tener en cuenta las dos cadenas complementarias o una sola.

Propiedad de encadenamiento • Esta propiedad de la estructura del ADN es la piedra angular para determinar la estructura y la secuenciación del ADN. • Por ejemplo, cuando los organismos vivos se reproducen cada uno de sus genes debe multiplicarse. Este proceso no ocurre generando una copia directa sino que se separan dos hebras de ADN y a partir de ellas se generan otras dos complementarias. • Por ello es fundamental comprender esta propiedad de complementariedad en su estructura. • La siguiente imagen representa esta situación.

Relación Proteína, DNA, RNA

Secuencias palíndromas en el ADN • ATGCTGA…. Y ….TCAGCAT corresponden a cadenas enfrentadas. • Otra propiedad fascinante adicional a la complementariedad del ADN es que a veces regiones de ADN pueden corresponder a secuencias que son idénticas cuando se leen desde las dos cadenas complementarias (en la dirección correspondiente). • Estas secuencias se denominan palíndromas porque la lectura de izquierda a derecha coincide con la lectura de derecha a izquierda.

Secuencias palíndromas en el ADN • Las secuencias palíndromas juegan un papel muy importante porque por ejemplo, la mayoría de las encimas restringidas del ADN, llamadas „cutting enzimes‟ tienen secuencias palíndromas y otras secuencias palíndromas sirven como „binding sites‟ (emplazamientos vinculantes), por este tipo de razones esta propiedad es fundamental en acciones de clasificación de secuencias. • Las secuencias palíndromas tienen una fuerte influencia en la estructura 3D de las moléculas de DNA y de RNA

Subsecuencias Palíndromas • Un ejercicio clásico en bioinformática es la búsqueda de subsecuencias palíndromas o casi palíndromas en secuencias de ADN.

El RNA • El ADN o ácido dexioribonucléico es el nucléico más conocido y dignificado de la familia de macromoléculas. • Su tarea es asegurar la conservación de la información genética en el organismo. • El ácido ribonucléico o RNA es un miembro más activo de la familia de los ácidos nucléicos: se sintetiza y se degrada constantemente creando copias de genes disponibles, a modo de fábrica de células.

El RNA

Diferencias entre el DNA y el RNA • Difieren en un único nucleótido: el uracil (U) en el RNA sustituye a la timina (T) en el DNA. • La forma de doble hélice en el DNA es una hélice simple en el RNA. • Debido a sus similitudes, muchos programas no se molestan en diferenciar la codificación y analizan las secuencias de RNA con la notación del DNA.

La estructura del RNA • Aunque la molécula de RNA consta de una única cadena de nucleótidos su tendencia natural es la búsqueda de emparejamientos con secuencias complementarias. • Aunque es una única cadena, se asemeja a la doble cadena del ADN porque se produce el plegado como puede observarse en la figura ; la forma final es de una hélice.

La estructura del RNA • Una vez sintetizada cada molécula de RNA adopta un plegado compacto rápidamente tratando de emparejar el máximo número de nucleótidos manteniendo la geometría de la cadena. • Los bucles (horquillas) son elementos básicos de la estructura. • La estructura 3D está hecha de nucleótidos C-V desemparejados (la horquilla) y de bases emparejadas (el resto). A estas parejas se les llama „stems‟. • La secuencia lineal de estos bloques y horquillas determinan la forma 3D final. La función de las moléculas de RNA también deriva de la forma 3D de su estructura como ocurre con el ADN.

Codificación del DNA • De los cientos de miles de secuencias de proteínas que actualmente contienen las Bases de Datos sólo un pequeño porcentaje corresponde a moléculas que han sido aisladas (por alguien o mediante algún experimento). • Determinar la secuencia de una proteína es mucho más difícil que determinar la secuencia de un ADN. • Todas las proteínas que un organismo dado puede sintetizar están codificadas como la secuencia de DNA de su genoma (tanto si es un microbio como si es un ser humano) • El atajo que usan los biólogos para leer las secuencias de proteínas es leer directamente la secuencia del DNA y extraer de esta secuencia el resto de la información. • De esta forma podemos conocer, por ejemplo, la secuencia de aminoácidos de una proteína aunque nunca haya sido aislada en un tubo de ensayo.

Transformación de ADN en proteínas. • Cuando se conoce una secuencia de DNA, ésta se puede traducir en la correspondiente secuencia de proteínas usando el código genético. • El código genético es universal (salvo algunas excepciones) • Es la solución para relacionar de forma única una secuencia de 4 nucleótidos con un juego de 20 aminoácidos. • Comprender cómo la célula hace esta transformación fue uno de los logros más importantes de la biología en los años 60. • La respuesta final se puede explicar en una pequeña tabla

El Código Genético

El Código Genético • Cómo usar la tabla de los códigos de la genética estándar : Paso 1. Leer la secuencia de ADN. Paso 2. Descomponerla en tripletas sucesivas continuas Paso 3. Traducir cada tripleta en el correspondiente aminoácido.

Ventajas de la codificación • Si la secuencia de ADN está correctamente orientada de 5‟ a 3‟ el resultado de la secuencia de proteína va también del término N al C. • Si se conoce dónde comienza la codificación de la proteína en la secuencia del ADN se puede intentar generar la correspondiente secuencia de aminoácidos usando programas de ordenador (“secuenciación de la proteína”) • Muchos programas de análisis de secuencias ofrecen este tipo de traducciones „on the fly‟ de forma que se pueden procesar secuencias de DNA como secuencias virtuales de proteínas ejecutando el algoritmo correspondiente.

Más observaciones relativas a la codificación de secuencias de DNA. • La proteína resultante de los procesos de secuenciación depende directamente del modo en que se convierten las secuencias de DNA en tripletas. • Se puede hacer como ejercicio las posibilidades del análisis de la cadena de una figura anterior. • Los resultados son diferentes si se comienza la codificación en la primera, en la segunda o en la tercera posición  Tres formas diferentes. • Teniendo en cuenta que la lectura del ADN puede realizarse de izquierda a derecha o al revés, hay seis posibilidades de traducción.

Más observaciones relativas a la codificación de secuencias de DNA. • Un intervalo de una secuencia de ADN que contenga un „stop‟ (traducción de TAA, TGA o TAG) se denomina un „open reading frame‟ (ORF) o estructura de lectura abierta que admite varias codificaciones. • Solo se utiliza una de las 6 posibilidades referidas para codificar cada región de ADN, pero algunas secuencias de ADN no son codificaciones de proteínas y también aparecen grandes trozos de ADN no codificado entre los genes de los organismos. • Gran parte de la bioinformática está dedicada al desarrollo de métodos para localizar regiones de proteína codificadas en las secuencias del DNA y determinar dónde comienzan y dónde finalizan los genes o dónde se interrumpen por intervalos no codificados (denominados „introns‟).

¿Qué estudia la bioinformática del DNA y del RNA? • Recuperación de secuencias de ADN de las bases de datos • Computación de la composición de nucleótidos • Identificación de lugares restrictivos • Identificación de ORFs • Cálculo del alineamiento óptimo entre dos o más secuencias de DNA • Ensamblar fragmentos de secuencias • Encontrar lugares polimórficos en genes • Etc.

Trabajando con el genoma completo • En 1977 se descubrió la primera técnica verdaderamente eficiente para la secuenciación del ADN. • En 1995 se determinó la primera secuencia de un genoma completo (el microbio Hemophilus infuezae). • En este periodo se crearon las herramientas informáticas más interesantes para la secuenciación del ADN: – programas para alineamiento de secuencias – métodos de clasificación de secuencias – algunas herramientas de visualización.

La genómica • La genómica es el estudio del mapa genético y se basa en el análisis completo de la secuencia del genoma mediante la secuenciación de genomas completos. • En la actualidad tenemos que trabajar con secuencias de DNA mucho más largas (desde aproximadamente un millón de bps para microbios hasta varios billones de bps de longitud para animales y humanos). • Esto supone unas herramientas informáticas capaces de almacenar, consultar, analizar y visualizar objetos enormes (como conjuntos de datos) de forma sencilla para los usuarios.

La genómica • En contraste con los análisis gen a gen que se realizaban en los inicios de la bioinformática, ahora las secuencias de ADN se obtienen frecuentemente sin un conocimiento previo de lo que hay realmente. En esencia, los genes son al mismo tiempo secuencias y descubrimiento de sus componentes. • Otras cosas que puede hacer la bioinformática por el estudio del genoma: – Encontrar qué genomas están disponibles en las bases de datos – Analizar secuencias en genomas específicos – Mostrar genomas mediante programas de visualización – Etc.

La genómica: Ejemplo. La figura representa el genoma completo de la bacteria Rickettsia conorii. Esta molécula de DNA circular es de 1.3 millones de bps de longitud. Cada rectangulito en los dos anillos más externos corresponde a una codificación de proteína del gen en el genoma circular. Cada rectangulito supone unos 1000 bps. Antes de comenzar la secuenciación de este genoma nadie conocía qué genes o proteínas había en esta bacteria así que casi todo lo que se conoce ahora sobre ella ha sido resultado del análisis por medio de la bioinformática.

RESUMEN: La información biológica • Los ácidos nucleicos (AN) contienen la información para generar los organismos: DNA  RNA  PROTEINAS  Función • Las proteínas se forman con aminoácidos (AA) unidos en secuencias lineales • Las instrucciones para definir la secuencia de AA están codificadas en los AN por grupos de tres nucleótidos, en un código genético redundante

2-Alineamiento de secuencias 07/03/2014 Introducción a la Bioinformática 102

1. Conceptos básicos 2. Métodos gráficos de alineamiento 3. Puntuación de los alineamientos 4. Programación dinámica 5. Métodos heurísticos 07/03/2014 Introducción a la Bioinformática 103

• El alineamiento de secuencias es probablemente la herramienta más utilizada en bioinformática • Su objetivo es alinear dos o más secuencias (de DNA o proteínas) de forma que puedan destacarse las regiones similares entre las moléculas • Al determinar si una secuencia desconocida es similar, en algún sentido, a secuencias conocidas (e idealmente de estructura y función conocidas) podremos identificarla y predecir su estructura y función 07/03/2014 Introducción a la Bioinformática 104

• Mediante un alineamiento global entre genomas se puede – identificar repeticiones internas (S1 vs S1) o – encontrar secuencias conservadas entre especies (S1 vs S2) • Para predecir la función de una proteína desconocida suele buscarse dominios funcionales comunes, – mediante alineamientos locales entre dos secuencias – mediante alineamientos múltiples entre conjuntos de secuencias • Para buscar una secuencia en una base de datos se alinean por separado distintos fragmentos y se cuantifica el grado de similitud alcanzado • Se pretende predecir la estructura de una secuencia identificándola con otras 07/03/2014 Introducción a la Bioinformática 105

• Existen muchos programas disponibles en WWW para alinear secuencias y buscarlas en las BD • Si se pretende que el resultado de dichos programas sea útil no deben ser “cajas negras” • La correcta elección del programa ( método) y de sus parámetros es muy importante – Una elección inadecuada puede conllevar la no detección de similitudes relevantes 07/03/2014 Introducción a la Bioinformática 106

• Alineamiento de dos secuencias – Métodos gráficos: Dotplot. Es intuitivo, pero difícil de cuantificar – Algoritmos óptimos de alineamiento global (NW) o local (SW) Obtienen el mejor alineamiento posible con programación dinámica Son demasiado exigentes para ser prácticos en búsquedas extensivas • Alineamientos múltiples • Algoritmos heurísticos para búsqueda en bases de datos FASTA, BLAST – Dan soluciones buenas, no necesariamente óptimas – Pueden ser mucho más rápidos 07/03/2014 Introducción a la Bioinformática 107

• Es el procedimiento consistente en comparar dos (“pairwise”) o más (“multiple”) secuencias buscando los caracteres o patrones que aparezcan en el mismo orden en las secuencias • Podemos distinguir entre alineamientos – Globales: Alineamiento de secuencias completas – Locales : Alineamiento de subsecuencias 07/03/2014 Introducción a la Bioinformática 108

2 Secuencias no alineadas L G P S S K L N I T K S Alineamiento global L G P S │ L N ▬ I T S A Alineamiento local ▬ ▬ ▬ ▬ ▬ ▬ ▬ T ▬ ▬ ▬ ▬ ▬ ▬ ▬ A T K │ K T G Q 07/03/2014 S Q A G K K G G A S I S M R R I L W G D D N A G │ G K │ K G │ G S ▬ S A I M G │ G K │ K G │ G ▬ ▬ ▬ ▬ ▬ ▬ ▬ ▬ Introducción a la Bioinformática R │ R I W L G D │ D N A ▬ ▬ ▬ ▬ ▬ ▬ ▬ ▬ 109

I I I M M N I I I 07/03/2014 A P F G R A M ▬ ▬ M P R N F ▬ I A L A A A N C I G C L A T B ▬ T ▬ B I L I I I L C E E A N A C A ▬ ▬ B LE B B B Introducción a la Bioinformática L L L E E E 110

07/03/2014 Introducción a la Bioinformática 111

• Se obtienen disponiendo dos secuencias S y T en los márgenes horizontal y vertical de una tabla • y marcando con una cruz (un punto) todas las posiciones en que coinciden los caracteres de S y T – Si son idénticas se observa una diagonal definida – Cuanto más diferentes sean, más difusa será – La aparición de patrones permite revelar estructuras en las secuencias 07/03/2014 Introducción a la Bioinformática 112

• Para facilitar la visualización, se opta a menudo por mostrar únicamente las diagonales formadas por un número mínimo de puntos (umbral de severidad). Cota que se fija como mínimo valor para mostrar la secuencia. • Si el umbral de severidad es alto  – Eliminamos el ruido de fondo (“filtrado alto”) – Solo detecta similitudes muy altas • Si es bajo  – Hay ruido de fondo – Detecta relaciones distantes En Softcomputing se denominan alfa-cortes 07/03/2014 Introducción a la Bioinformática 113

07/03/2014 Introducción a la Bioinformática 114

07/03/2014 Introducción a la Bioinformática 115

07/03/2014 Introducción a la Bioinformática 116

07/03/2014 Introducción a la Bioinformática 117

• Para cuantificar la similitud entre dos cadenas, S y T, definimos sistemas de puntuaciones de forma que para cada alineamiento se pueda calcular un número tal que, a mayor valor, mayor sea su significación (biológica) • Pueden ser esquemas sencillos como por ej – Coincidencia , S[i]=T[i]  1, – No coincidencia, S[i]#T[i]  0, – Inserción de espacios (gaps)  -1, • o bien sistemas más complejos basados en afinidades químicas o en frecuencias de emparejamiento observadas 07/03/2014 Introducción a la Bioinformática 118

• Una vez establecido un sistema de puntuación la puntuación de una pareja de caracteres s,t alineados se define como p(s,t) • La puntuación (score) de un alineamiento entre S y T p ( s, t ) p S [i ], T [i ] i • Un alineamiento es óptimo si su puntuación es la más grande posible 07/03/2014 Introducción a la Bioinformática 119

S= T= p(s,t) T T 1 G A 0 C A 0 A G 0 G T 0 T S= T= p(s,t) A A 1 T T 1 G A 0 C A 0 A ▬ -1 G G 1 T T 1 3 S= T= p(s,t) 07/03/2014 A A 1 A A 1 T T 1 G ▬ -1 C A 0 A A 1 G G 1 T T 1 4 Introducción a la Bioinformática 2 120

Puntuación con esquema simple S= T= p(s,t) S= T= p(s,t) 07/03/2014 T -1 T T 1 Y G 0 G Y 0 A A 1 P P 1 P P 1 W P 0 C W 0 S S 1 T T 1 T G 0 Y Y 1 G A 0 A P 0 P P 1 P P 1 W W 1 C S 0 S Introducción a la Bioinformática -1 4 4 121

• Los dos alineamientos del ejemplo anterior puntúan igual. Sin embargo – a) conserva residuos comunes (T,A, P, S) – b) conserva residuos menos habituales (W, Y) • El sistema de puntuar los emparejamientos entre AA debería reflejar su relación química y biológica – Residuos similares/distintos deberían puntuar alto/bajo pues el cambiar uno por otro afectará poco/mucho la función de la proteína 07/03/2014 Introducción a la Bioinformática 122

• Una forma usual de definir el sistema de puntuación es utilizando una matriz de sustitución • Es una tabla que contiene las puntuaciones que asignamos a cada pareja posible (sirve para las coincidencias y las no-coincidencias) • El término „sustitución‟ refleja que lo que se pretende al puntuar un emparejamiento es valorar el coste evolutivo de cambiar un residuo por otro 07/03/2014 Introducción a la Bioinformática 123

Secuencia 1 actaccagttcatttgatacttctcaaa Secuencia 2 Matriz identidad P(i,i)=1, P (i,j)=0 o alguna variante P(i,i)=0.9, P (i,j)=-0.1 07/03/2014 taccattaccgtgttaactgaaaggacttaaagact A G C T A 1 0 0 0 G 0 1 0 0 C 0 0 1 0 T 0 0 0 1 Introducción a la Bioinformática Match: 1 Mismatch: 0 Score = 5 124

• Los AA tienen distintas propiedades  posibilidades distintas de ser sustituidos unos por otros en la tiny evolucion aliphatic P C S+S I V A L hydrophobic M Y F small G G CSH T S D K W H N E R Q aromatic positive polar charged 07/03/2014 Introducción a la Bioinformática 125

• Las matrices de puntuación se construyen para que reflejen: – El nº de mutaciones necesario para convertir una secuencia en otra – La similaridad química – Las frecuencias de mutación observadas – La probabilidad de ocurrencia de cada AA. • La más utilizadas son las PAM y las BLOSUM – PAM: Point Accepted Mutation Matrix – BLOSUM: BLOcks SUbstitution Matrix 07/03/2014 Introducción a la Bioinformática 126

• No hay una matriz única que se pueda usar siempre. • Pero se pueden escoger según la familia de proteínas y grado de similitud esperado. • PAM – Derivadas de alineamientos globales de secuencias próximas – A mayor número asumimos que hay nº mayor distancia evolutiva – Mínimo: PAM40 (secs. Similares)  Máx: PAM250 (secs distantes) • BLOSUM – Derivadas de alineamientos locales de secuencias distantes – A mayor número asumimos que mayor proximidad evolutiva – Minimo: BLOSUM90 Maximo: BLOSUM45 (El nº representa porcentaje de identifdad) 07/03/2014 Introducción a la Bioinformática 127

• Ciertas sustituciones de AA son muy comunes en proteínas homólogas. Otras no lo son en absoluto. • Esto puede interpretarse como que: – Las primeras mantienen la función de la proteína (existencia de homología) – Las segundas afectan negativamente a su función (ausencia de homología) • Las sustituciones “inusuales” tendrán menor grado de aceptación por por parte de la selección natural. • Para poder hacer alineamientos que reflejen el proceso evolutivo que ha llevado a cambiar una secuencia por otra es preciso disponer de estimaciones de la frecuencia con que se produce cada cambio o sustitución. • Para responder a esta necesidad se crearon las matrices de sustitución. a la Bioinformática 07/03/2014 Introducción 128

• En la construcción de matrices de sustitución se utilizaron dos tipos de modelos probabilísticos para las sustituciones. – Modelo de homología: La probabilidad de una substitución entre dos AA1 y AA2 depende de si se ve favorecida o no por la evolución. – Modelo nulo: La probabilidad de observar una sustitución depende tan solo de la probabilidad con que se encuentra AA1 y AA2 en la población. 07/03/2014 Introducción a la Bioinformática 129

• • • • La probabilidad de las substituciones bajo el modelo de homología se estima a partir de alineamientos entre secuencias de relación conocida. El valor qij es una estimación de la probabilidad de la sustitución La probabilidad de las sustituciones bajo el modelo nulo se estima simplemente como el producto de las probabilidades de que el aa i sustituya y el aa j sea sustituido. El cociente entre ambas probabilidades nos da una idea de que resulta más verosímil – – 07/03/2014 Hay homología (R > 1, log(R) > 0) Sustitución al azar (R < 1, log(R) < 0) Introducción a la Bioinformática 130

• Las matrices de sustitución contienen para cada sustitución el logaritmo de la razón entre la probabilidad de la sustitución suponiendo homología o suponiendo que se producen al azar. – Si la sustitución se ve favorecida por la selección será más probable observarla que lo que seria de esperar del simple azar  El cociente será superior a uno y el logaritmo positivo. – Si la sustitución se ve desfavorecida por la selección será más plausible observarla por azar que porque se haya conservado evolutivamente  El cociente será menor que uno y el logaritmo negativo. • Las sustituciones con valores positivos en las matrices de sustitución suele corresponderse con AA cuyas propiedades fisicoquímicas son similares. 07/03/2014 Introducción a la Bioinformática 131

• Derivadas de alineamientos globales de familias de proteínas. • Dayhoff et al., 1978 escogieron familias de proteínas cuyos miembros presentaran como mínimo un 85% de identidad. – Para cada familia se construyeron árboles filogenéticos – Se calculó el número de sustituciones para cada aminoácido • El número de sustituciones se utilizó para calcular las matrices PAM-1, que representan aquella situación en que en promedio ha habido sustituciones en tan sólo el 1% de las posiciones. • La construcción de matrices para mayores tasas de sustituciones se realiza mediante un modelo de Markov a partir de la matriz PAM-1. – PAM250 = 250 mutaciones por 100 residuos • Cuanto mayor es el número estamos suponiendo una mayor distancia entre las secuencias que deseamos alinear. 07/03/2014 Introducción a la Bioinformática 132

PAM 250 A R N D C Q E G H I L K M F P S T W W Y V B Z 07/03/2014 A 2 -2 0 0 -2 0 0 1 -1 -1 -2 -1 -1 -3 1 1 1 -6 -3 0 2 1 R -2 6 0 -1 -4 1 -1 -3 2 -2 -3 3 0 -4 0 0 -1 2 -4 -2 1 2 N 0 0 2 2 -4 1 1 0 2 -2 -3 1 -2 -3 0 1 0 -4 -2 -2 4 3 D 0 -1 2 4 -5 2 3 1 1 -2 -4 0 -3 -6 -1 0 0 -7 -4 -2 5 4 C C -2 -4 -4 -5 12 -5 -5 -3 -3 -2 -6 -5 -5 -4 -3 0 -2 -8 0 -2 -3 -4 Q 0 1 1 2 -5 4 2 -1 3 -2 -2 1 -1 -5 0 -1 -1 -5 -4 -2 3 5 -8 E 0 -1 1 3 -5 2 4 0 1 -2 -3 0 -2 -5 -1 0 0 -7 -4 -2 4 5 G 1 -3 0 1 -3 -1 0 5 -2 -3 -4 -2 -3 -5 0 1 0 -7 -5 -1 2 1 H -1 2 2 1 -3 3 1 -2 6 -2 -2 0 -2 -2 0 -1 -1 -3 0 -2 3 3 I -1 -2 -2 -2 -2 -2 -2 -3 -2 5 2 -2 2 1 -2 -1 0 -5 -1 4 -1 -1 L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6 -3 4 2 -3 -3 -2 -2 -1 2 -2 -1 K -1 3 1 0 -5 1 0 -2 0 -2 -3 5 0 -5 -1 0 0 -3 -4 -2 2 2 M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6 0 -2 -2 -1 -4 -2 2 -1 0 F -3 -4 -3 -6 -4 -5 -5 -5 -2 1 2 -5 0 9 -5 -3 -3 0 7 -1 -3 -4 P 1 0 0 -1 -3 0 -1 0 0 -2 -3 -1 -2 -5 6 1 0 -6 -5 -1 1 1 Introducción a la Bioinformática S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 2 1 -2 -3 -1 2 1 T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -3 0 1 3 -5 -3 0 2 1 W W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17 0 -6 -4 -4 Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10 -2 -2 -3 17 V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 -2 4 0 0 B 2 1 4 5 -3 3 4 2 3 -1 -2 2 -1 -3 1 2 2 -4 -2 0 6 5 Z 1 2 3 4 -4 5 5 1 3 -1 -1 2 0 -4 1 1 1 -4 -3 0 5 6 133

BLOSUM (Blocks Substitution Matrix) • Derived from alignments of domains of distantly related proteins (Henikoff & Henikoff,1992). A A C E C • Occurrences of each amino acid pair in each column of each block alignment is counted. A A C • The numbers derived from all blocks were E used to compute the BLOSUM matrices. C 07/03/2014 Introducción a la Bioinformática A- C = 4 A- E = 2 C-E =2 A-A = 1 C-C =1 134

BLOSUM (Blocks Substitution Matrix) • Sequences within blocks are clustered according to their level of identity. • Clusters are counted as a single sequence. • Different BLOSUM matrices differ in the percentage of sequence identity used in clustering. • The number in the matrix name (e.g. 62 in BLOSUM62) refers to the percentage of sequence identity used to build the matrix. • Greater numbers mean smaller evolutionary distance. 07/03/2014 Introducción a la Bioinformática 135

TIPS on choosing a scoring matrix • Generally, BLOSUM matrices perform better than PAM matrices for local similarity searches (Henikoff & Henikoff, 1993). • When comparing closely related proteins one should use lower PAM or higher BLOSUM matrices, for distantly related proteins higher PAM or lower BLOSUM matrices. • For database searching the commonly used matrix is BLOSUM62. 07/03/2014 Introducción a la Bioinformática 136

• En un sistema de puntuación es importante definir el coste de insertar o eliminar un residuo, lo que en el alineamiento aparece como un hueco (“gap”) • Suele penalizarse distinto – el primer hueco (“gap opening”) – que los restantes (“gap extension”) que parten de él • La variación de estos parámetros puede tener efectos importantes en el alineamiento final 07/03/2014 Introducción a la Bioinformática 137

Coste de apertura de gap Coste de extensión del gap Grande Grande Pocas inserciones o eliminaciones Bueno para proteínas muy relacionadas Grande Pequeño Algunas inserciones grandes Bueno si puede que se hayan insertado dominios completos Pequeño Grande Muchas inserciones pequeñas Bueno si se trata de proteínas distantes 07/03/2014 Comentario Introducción a la Bioinformática 138

07/03/2014 Introducción a la Bioinformática 139

• Un algoritmo para obtener el alineamiento óptimo es: – Construir todos los posibles alineamientos – Calcular la puntuación de cada uno – El alineamiento óptimo es el que obtenga el valor más grande (puede haber más de uno!) • El número de alineamientos posibles es muy alto: Si S, T constan de unos 20 caracteres pueden hacer falta más de 240 operaciones!!! 07/03/2014 Introducción a la Bioinformática 140

• La idea básica de la programación dinámica es una técnica de diseño de algoritmos consistente en – Considerar, en primer lugar, los casos más sencillos de un problema – Resolverlos – Combinarlos para obtener la solución de casos más complicados – Hasta resolver el caso completo original 07/03/2014 Introducción a la Bioinformática 141

• Los dos más conocidos son – Needleman y Wunsch (1970) para alineamientos globales – Smith y Waterman (1981), una variante para alineamientos locales • Sirven para alinear tanto DNA como proteínas • Cada algoritmo retorna los alineamientos con la máxima puntuación posible para una matriz de substitución y un coste de “gaps” dados • El alineamiento obtenido no tiene necesariamente un significado biológico 07/03/2014 Introducción a la Bioinformática 142

143

• Problema del ascensor (variante del famoso problema de la mochila) • Función objetivo 1: Maximizar el número de personas que transportará el ascensor • Función objetivo 2: Maximizar el peso que transportará el ascensor • Datos: – Capacidad del ascensor C=300kg – Pesos de las personas en espera: 30, 40, 50, 70, 90, 150 • Criterio voraz 1: Escoger en cada etapa la persona de menor peso • Criterio voraz 2: Escoger en cada etapa la persona de 144 mayor peso

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

Alineamiento de Secuencias Se denomina alineamiento de secuencias en bioinformática al proceso de representar y comparar dos o más secuencias o cadenas de ADN o ARN para resaltar sus zonas de similitud, con el fin de descubrir relaciones funcionales o evolutivas entre los genes o proteínas de donde proceden dichas cadenas. Las secuencias alineadas se escriben con los símbolos (códigos) de aminoácidos o nucleótidos en filas de una matriz en las que, si es necesario, se insertan espacios para que las zonas con idéntica o similar estructura se alineen. Cuando dos secuencias en un alineamiento comparten un ancestro común, las no coincidencias pueden interpretarse como mutaciones puntuales y los huecos del alineamiento como mutaciones de inserción o delección introducidas en uno o en ambos linajes en el tiempo que transcurrió desde que divergieron. 166

Alineamiento de Secuencias 167

Alineamiento de Secuencias • En secuencias de proteínas el grado de similitud entre los aminoácidos en posiciones concretas se interpreta como medida de conservación de una región particular entre linajes. • La ausencia de sustituciones o presencia de sustituciones muy conservadas tiene importancia estructural o funcional. • De esta forma el alineamiento de secuencias se utiliza para obtener conclusiones de similitud-no similitud entre las secuencias y deducir propiedades, funcionalidades, etc. • Las técnicas de alineamiento de secuencias también pueden utilizarse con otros tipos de secuencias de símbolos y caracteres para identificación de similitudes en series de letras y palabras del lenguaje humano y también en análisis de datos financieros. 168

Alineamiento de Secuencias Representación de alineamientos Se representan normalmente con un formato gráfico y de texto. En casi todas las representaciones de alineamientos se escriben las secuencias en filas de forma que los residuos alineados aparecen en columnas sucesivas, como se muestra en la siguiente figura. 169

Alineamiento de Secuencias Las columnas alineadas contienen caracteres idénticos o similares. Muchos programas de visualización de secuencias utilizan también esquemas coloreados para mostrar información de las propiedades, por ejemplo, en secuencias de ADN y ARN se asigna a cada base su propio color. Los alineamientos de secuencias pueden almacenarse en una gran variedad de formatos y muchos de estos formatos han sido desarrollados para atender la ejecución de algún programa de alineamiento por lo que muchas veces el formato está asociado al programa, como el formato FASTA y el GenBank. A veces esto provoca problemas de compatibilidad. 170

Tipos de alineamiento Hay tres tipos fundamentales: global, local e híbrido. • Los alineamientos globales intentan alinear cada residuo de cada secuencia. Son más útiles cuando las secuencias iniciales son similares y aproximadamente del mismo tamaño. El algoritmo de Needleman-Wunsch, basado en programación dinámica, es un ejemplo de estrategia general de alineamiento global basado en Programación Dinámica • Los alineamientos locales son más útiles para secuencias diferenciadas en las que se sospecha que existen regiones muy similares. • El algoritmo de Smith-Waterman es un método general de alineamiento local basado en Programación Dinámica • Los métodos híbridos también son conocidos como semiglobales o “glocales” intentan encontrar el mejor alineamiento que incluya el inicio y el final de una u otra secuencia. 171

Alineamientos globales: Algoritmo de Needleman-Wunsch El algoritmo Needleman-Wunsch realiza un alineamiento global de dos secuencias (aquí llamadas A y B). Usado en bioinformática para alinear secuencias de nucleótidos o proteínas. Fue propuesto en 1970 por Saul Needleman y Christian Wunsch en el artículo “A general method applicable to the search for similarities in the amino acid sequence of two proteins”, J Mol Biol. 48(3):443-53. El algoritmo Needleman–Wunsch es un ejemplo de programación dinámica, y está garantizado que encuentra el alineamiento con la puntuación máxima. Needleman–Wunsch fue la primera aplicación de programación dinámica para la comparación de secuencias biológicas. 172

Alineamientos globales: Algoritmo de Needleman-Wunsch La puntuación para caracteres alineados está especificada por una matriz de similitud S(i,j) cuyos valores denotan la similitud de los caracteres i y j de las respectivas secuencias en comparación. Esta usa una penalidad por hueco (gap) lineal, aquí llamada d. Por ejemplo, si la matriz de similitud es: Entonces el alineamiento es: AGACTAGTT AC CGA - - -GACGT 173

Con una penalidad por hueco de -5, tendríamos la siguiente puntuación: Alineamientos globales: Algoritmo de Needleman-Wunsch AG AC TA GTTAC CGA - - - GACGT 174

Alineamientos globales: Algoritmo de Needleman-Wunsch Para encontrar el alineamiento con más puntuación se utilizan matrices bidimensionales. En la matriz bidimensional F hay una columna por cada carácter de la secuencia A, y una fila para cada carácter de la secuencia B. Así si estamos alineando secuencias de tamaños n y m, el tiempo de ejecución del algoritmo es proporcional a la dimensión de la matriz F, es decir, de orden O(nxm) y la cantidad de memoria utilizada también es del mismo orden O(nxm). Sin embargo hay una versión modificada del algoritmo que usa solo O(n+m) espacio, al costo de un tiempo de ejecución más grande. Esta modificación es de hecho una técnica general que aplicamos a muchos algoritmos de programación dinámica; este método fue introducido en el algoritmo de Hirschberg para resolver el problema de la subsecuencia común más larga. 175

Alineamientos globales: Algoritmo de Needleman-Wunsch Cuando el algoritmo progresa, el elemento Fij de la matriz puede ser asignado para ser la puntuación óptima para el alineamiento de los primeros i caracteres en A y los primeros j caracteres en B. El principio de optimización es entonces aplicado como se describe mediante las ecuaciones recurrentes: F(0,j) = d * j F(i,0) = d * i F(i,j) = max(F(i − 1,j − 1) + S(Ai − 1,Bj − 1),F(i,j − 1) + d,F(i − 1,j) + d) 176

Alineamientos globales: Algoritmo de Needleman-Wunsch El pseudo-código del algoritmo que calcula la matriz A es el siguiente: for i=0 a long(A)-1 F(i,0)  d*i for j=0 a long(B)-1 F(0,j)  d*j for i=1 a long(A) for j = 1 a long(B) { Elección1  F(i-1,j-1) + S(A(i-1), B(j-1)) Elección2  F(i-1, j) + d Elección3  F(i, j-1) + d F(i,j)  max(Elección1, Elección2, Elección3) } 177

Alineamientos globales: Algoritmo de Needleman-Wunsch Una vez que la matriz F está calculada, la puntuación máxima para cualquier alineamiento se encuentra en la esquina inferior derecha de la matriz. Para calcular cuál es el alineamiento que produce esa puntuación, empezando desde la celda que se encuentra al fondo a la derecha, y comparar el valor con las tres posibles fuentes (Elección1, Elección2, Elección3) para ver de donde proviene. Si era Elección1, entonces A(i) y B(i) están alineadas, si era Elección2 entonces A(i) está alineado con un gap, y si era Elección3, entonces B(i) está alineada con un gap. 178

Alineamientos globales: Algoritmo de Needleman-Wunsch AlineamientoA  “” AlineamientoB  “” i  long(A) j  long(B) while (i > 0 AND j > 0) { Score  F(i,j) ScoreDiag  F(i – 1, j – 1) ScoreUp  F(i, j – 1) ScoreLeft  F(i – 1, j) if (Score == ScoreDiag + S(A(i-1), B(j-1))) { AlineamientoA  A(i-1) + AlineamientoA AlineamientoB  B(j-1) + AlineamientoB ii–1 jj–1 } else if (Score == ScoreLeft + d) { AlineamientoA  A(i-1) + AlineamientoA AlineamientoB  “-” + AlineamientoB ii–1 } otherwise (Score == ScoreUp + d) { AlineamientoA  “-” + AlineamientoA AlineamientoB  B(j-1) + AlineamientoB jj–1 } } while (i > 0) { AlineamientoA  A(i-1) + AlineamientoA AlineamientoB  “-” + AlineamientoB i <- i – 1 } while (j > 0) { AlineamientoA  “-” + AlineamientoA AlineamientoB  B(j-1) + AlineamientoB jj–1 } 179

Alineamientos locales: Algoritmo Smith-Waterman El algoritmo Smith-Waterman es un famoso algoritmo para realizar alineamientos locales de secuencias; esto es, determinar regiones similares entre dos secuencias de nucleótidos o proteínas. El algoritmo fue propuesto por Temple Smith y Michael Waterman en 1981. Como el algoritmo Needleman-Wunsch, del cual es una variación, Smith-Waterman es un algoritmo de programación dinámica. Como tal, posee la atractiva propiedad que garantiza encontrar el alineamiento local óptimo con respecto al sistema de puntaje que está siendo utilizado (que incluye la matriz de sustitución y el plan de puntaje con interrupciones). La principal diferencia con el algoritmo Needleman-Wunsch es que las celdas negativas de las matrices de puntuación se inicializan a cero, lo cual hace que los alineamientos locales sean visibles. 180

Alineamientos locales: Algoritmo Smith-Waterman El retroceso comienza en la celda de la matriz con el puntaje más alto y continua hasta que una celda con puntaje cero es encontrada, proporcionando el puntaje más alto para el alineamiento local. Una motivación para alineamientos locales es la dificultad para obtener alineamientos correctos en regiones de baja similitud entre secuencias biológicas lejanamente emparentadas, porque las mutaciones agregaron mucho “ruido” con la evolución para permitir una comparación significativa de estas regiones. Los alineamientos locales evitan estas regiones completamente y se concentran en aquellas con un puntaje positivo, por ejemplo, aquellas con señales de similitud conservadas por la evolución. Una prerrequisito para alineamientos locales es una expectativa de puntaje negativo. La expectativa de puntaje es definida como el puntaje promedio que el sistema de puntaje (matriz de sustitución y penalidades por huecos) puede proporcionar para una secuencia aleatoria. 181

Alineamientos locales: Algoritmo Smith-Waterman Otro motivo para usar alineamientos locales es que existe un modelo estadístico confiable (desarrollado por Karlin y Altschul) para alineamientos locales óptimos. El alineamiento de secuencias no relacionadas tiende a producir puntajes de alineamiento local óptimos que siguen una distribución de valores extrema. Esta propiedad permite a los programas producir un valor esperado para el alineamiento óptimo de dos secuencias, el cual es una medida de la frecuencia con que dos secuencias podrían producir un alineamiento óptimo cuyo puntaje es mayor o igual al puntaje observado. Valores muy bajos de expectativa indican que las dos secuencias pueden ser homólogas, lo que significa que podrían tener un ancestro en común. Sin embargo, el algoritmo Smith-Waterman es bastante demandante de recursos de tiempo y memoria: para alinear dos secuencias de longitudes m y n, el tiempo y el espacio requerido son O(mxn). Como resultado, en la práctica es remplazado principalmente por el algoritmo BLAST que si bien no garantiza encontrar los alineamientos óptimos, es mucho más eficiente. 182

1. 2. 3. 4. La bioinformática y las bases de datos Las bases de datos en biología molecular Formato de la información almacenada Herramientas de búsqueda Introducción a la Bioinformática 184

• El proyecto genoma humano y similares genera un inmenso flujo de información • Para poder utilizar esta información, ha de estar almacenada correctamente • El acceso a la información almacenada ... – Ha de ser rápido – Debe poder hacerse de manera flexible • Esto es posible gracias a la creación de bases de datos y distribución vía Internet. Introducción a la Bioinformática 185

• Búsqueda de información. – Por palabra clave, números de acceso, autores... • Búsqueda de homologías – ¿Hay secuencias igual o parecidas a la mía ? • Búsqueda de patrones – ¿Mi secuencia contienen patrones conocidos? • Predicciones – ¿Puedo encontrar proteínas parecidas a la mía, pero con función conocida? Introducción a la Bioinformática 186

• Los proveedores de recursos – Centros o organizaciones especializadas en tener y mantener las bases de datos. • Bases de datos – Hay mucha variedad y contiene información diversa • Las herramientas – Para encontrar información en las BD – Para contrastar secuencias contra las BD – Para exportar la información Introducción a la Bioinformática 187

• El National Center for Biotechnology Information (NCBI) centraliza los bancos de datos y aplicacions de EEUU • El European Bioinformatics Institute (EBI) realiza una función similar en Europa • GenomeNet reune bases de datos diversas en Japón Introducción a la Bioinformática 188

• Existen cientos de BD en número tan elevado que no es práctico enumerarlas (aunque aquí lo intentan) • Por el tipo de información que contienen distinguimos – – – – – – Bases de datos bibliográficas Bases de datos taxonómicas Bases de datos de nucleótidos Bases de datos genómicas Bases de datos de proteinas Bases de datos de microarrays Introducción a la Bioinformática 189

• Organización de los artículos publicados en la revistas de ámbito científico. – Pubmed (NCBI) – Medline (EBI) – Biocatalog: organización de los artículos por temáticas concretas de biología molecular. Introducción a

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Dynamic programming and sequence alignment

Back to top. Dynamic programming. Dynamic programming is an algorithmic technique used commonly in sequence analysis. Dynamic programming is used ...
Read more

3. Algorithm for sequence alignment: dynamic programming

Stockholm Bioinformatics Center, SBC ... Algorithm for sequence alignment: ... Please note that there are other variants of dynamic programming in sequence ...
Read more

Dynamic Programming Tutorial - Avatar Software AB

Dynamic Programming The following is an example of global sequence alignment using Needleman/Wunsch techniques. For this example, ...
Read more

Multiple sequence Alignment - Bioinformatics and Biostatistics

Multiple sequence Alignment ... I managed to code for sequence alignment for 2 sequences but have trouble to ... It requires double dynamic programming.
Read more

Statement of Problem Pairwise Sequence Alignment using ...

Pairwise Sequence Alignment using Dynamic Programming Russ B. Altman, MD, PhD BMI 214 CS 274 ... Sequence alignment can be formulated as a transducer.
Read more

Sequence Alignment and Dynamic Programming

Sequence Alignment and Dynamic Programming Lecture 1 ... Local Alignment Dynamic Programming . Intro to Local Alignments • Statement of the problem
Read more

Multiple Sequence Alignment: Multi- dimensional Dynamic ...

dimensional Dynamic Programming Zhiping Weng Boston University BE561 10/23/00 Zhiping Weng ... Multiple Alignment of 3 Sequences: Dynamic Programming
Read more

Versatile and declarative dynamic programming using pair ...

Dynamic programming is a widely used programming technique in bioinformatics. ... sequence analysis, dynamic programming ... sequence alignment ...
Read more

Bioinformatics part 3 Sequence alignment introduction ...

Bioinformatics part 3 Sequence alignment ... In bioinformatics, a sequence alignment is a ... on dynamic programming. Local alignments are ...
Read more