Técnicas y Herramientas Bioinformáticas

• Horas semanales
• Competencias
• Objetivos
• Contenidos
• Actividades
• Metodología docente
• Método de evaluación
• Bibliografía
• Capacidades previas

Profesorado

Responsable

• Santiago Marco Sola ( )

Horas semanales

Competencias

Competencias Técnicas de cada especialidad

Dirección y gestión

• CDG1 - Capacidad para la integración de tecnologías, aplicaciones, servicios y sistemas propios de la Ingeniería Informática, con carácter generalista, y en contextos más amplios y multidisciplinares.

Específicas

• CTE7 - Capacidad para comprender y poder aplicar conocimientos avanzados de computación de altas prestaciones y métodos numéricos o computacionales a problemas de ingeniería.
• CTE9 - Capacidad para aplicar métodos matemáticos, estadísticos y de inteligencia artificial para modelar, diseñar y desarrollar aplicaciones, servicios, sistemas inteligentes y sistemas basados en el conocimiento.

Competencias Técnicas Genéricas

Genéricas

• CG4 - Capacidad para el modelado matemático, cálculo y simulación en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación, desarrollo e innovación en todos los ámbitos relacionados con la Ingeniería en Informática.

Competencias Transversales

Uso solvente de los recursos de información

• CTR4 - Gestionar la adquisición, la estructuración, el análisis y la visualización de datos e información del ámbito de la ingeniería informática y valorar de forma crítica los resultados de esta gestión.

Básicas

• CB6 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.

Objetivos

1. Comprender algoritmos y estructuras de datos de coincidencia de patrones y su implementación en un lenguaje de programación moderno, y aplicarlos para resolver problemas prácticos en bioinformática.
   Competencias relacionadas: CB6, CTR4, CDG1, CTE7, CTE9, CG4,

Contenidos

1. Tecnologías de secuenciación y análisis del genoma
   Se presenta una visión general de las tecnologías modernas de secuenciación de ADN y de las características computacionales de los datos genómicos. Se presentan las principales tareas del análisis genómico, incluyendo el mapeo de secuencias, el variant calling y el ensamblaje de secuencias. Estos problemas motivan la abstracción de las secuencias biológicas como cadenas y ponen de relieve los retos algorítmicos y computacionales que plantean los conjuntos de datos a escala genómica.
2. Algoritmos de búsqueda exacta de patrones
   Se estudia el problema de la búsqueda exacta como tarea algorítmica fundamental. Se presentan algoritmos clásicos para ilustrar distintos paradigmas de diseño, incluyendo el preprocesamiento basado en prefijos, las estrategias heurísticas de salto, las técnicas de hashing y el paralelismo a nivel de bit. Se hace énfasis en la corrección, la complejidad temporal y las consideraciones prácticas de rendimiento.
3. Estructuras de datos para la indexación de texto
   Este bloque se centra en estructuras de datos que permiten una búsqueda eficiente de patrones sobre textos de gran escala, con especial atención a aplicaciones genómicas. Se cubren estrategias de indexación basadas en hashing y en k-mers, estructuras de árboles lexicográficos, árboles de sufijos y arrays de sufijos, así como índices comprimidos de texto completo basados en la transformada de Burrows-Wheeler.
4. Algorithmos de búsqueda aproximada de patrones
   Este bloque presenta la búsqueda aproximada de patrones de texto, donde se permiten diferencias. El bloque introduce modelos de distancia y error, seguidos de técnicas de filtrado y seeding para reducir el espacio de búsqueda. Se presentan métodos asistidos por índice, estimación de similitud mediante sketches, algoritmos de verificación y estrategias de chaining como componentes clave de los algoritmos y herramientas modernas de búsqueda aproximada.
5. Alineamiento de secuencias
   Este bloque aborda el alineamiento de secuencias como tarea fundamental en bioinformática y análisis genómico. Se introducen técnicas de programación dinámica para calcular la distancia de edición y otros modelos de alineamiento, incluyendo gap-affine. Se estudian modalidades clásicas de alineamiento y optimizaciones algorítmicas avanzadas, con atención a la eficiencia espacial, al sparse dynamic programming y a métodos output-sensitive, como el Wavefront Alignment Algorithm.
6. Grafos de secuencia y pangenómica
   La asignatura concluye con una introducción a representaciones basadas en grafos para modelar variación genómica. Se discuten grafos de secuencia, modelos de pangenoma y su relación con las referencias lineales. Se introduce el problema de alineamiento de secuencias sobre grafos, destacando los retos y las oportunidades algorítmicas que surgen al extender técnicas de alineamiento a estas representaciones.

Actividades

Actividad Acto evaluativo

Metodología docente

Método de evaluación

Bibliografía

Básica:

• Genome-scale algorithm design : bioinformatics in the era of high-throughput sequencing - Mäkinen, Veli; Belazzougui, Djamal; Cunial, Fabio; Tomescu, Alexandru I, Cambridge University Press, 2023. ISBN: 9781009341233
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991005219277706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms on strings, trees, and sequences : computer science and computational biology - Gusfield, Dan, Cambridge University Press, 1997. ISBN: 978- 0521585194
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001989459706711&context=L&vid=34CSUC_UPC:VU1
• Biological sequence analysis [Recurs electrònic] : probabilistic models of proteins and nucleic acids - Durbin, Richard, Cambridge University Press, 1998. ISBN: 978-0521629713
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000581539706711&context=L&vid=34CSUC_UPC:VU1

Complementaria:

• Bioinformatics : sequence and genome analysis - Mount, David W, Cold Spring Harbor Laboratory Press , cop. 2004. ISBN: 0879696877
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002934579706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• An Introduction to bioinformatics algorithms - Jones, Neil C; Pevzner, Pavel, MIT Press , cop. 2004. ISBN: 978-0262101066
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002778129706711&context=L&vid=34CSUC_UPC:VU1

Capacidades previas