Techniques and Tools for Bioinformatics

• Weekly hours
• Competences
• Objectives
• Contents
• Activities
• Teaching methodology
• Evaluation methodology
• Bibliography
• Previous capacities

Teachers

Person in charge

• Santiago Marco Sola ( )

Weekly hours

Competences

Technical Competences of each Specialization

Direcció i gestió

• CDG1 - Capability to integrate technologies, applications, services and systems of Informatics Engineering, in general and in broader and multicisciplinary contexts.

Especifics

• CTE7 - Capability to understand and to apply advanced knowledge of high performance computing and numerical or computational methods to engineering problems.
• CTE9 - Capability to apply mathematical, statistical and artificial intelligence methods to model, design and develop applications, services, intelligent systems and knowledge-based systems.

Generic Technical Competences

Generic

• CG4 - Capacity for mathematical modeling, calculation and simulation in technology and engineering companies centers, particularly in research, development and innovation tasks in all areas related to Informatics Engineering.

Transversal Competences

Information literacy

• CTR4 - Capability to manage the acquisition, structuring, analysis and visualization of data and information in the area of informatics engineering, and critically assess the results of this effort.

Basic

• CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.

Objectives

1. Understand pattern matching algorithms and data structures and their implementation in a modern programming language, and apply them to solve practical problems in bioinformatics.
   Related competences: CB6, CTR4, CDG1, CTE7, CTE9, CG4,

Contents

1. Sequencing Technologies and Genome Analysis
   The course gives an overview of modern DNA sequencing technologies and the computational characteristics of genomic data. We introduce the main sources of error and variability in sequencing data and review fundamental genome analysis tasks, including read mapping, variant calling, and assembly. These problems motivate the abstraction of biological sequences as strings and highlight the algorithmic and computational challenges posed by genome-scale datasets.
2. Exact String Matching Algorithms
   We study the exact string matching problem as a foundational algorithmic task. Classical algorithms are introduced to illustrate different design paradigms, including prefix-based preprocessing, heuristic skipping strategies, hashing, and bit-parallelism. Emphasis is placed on correctness, time complexity, and practical performance considerations.
3. Text-Indexing Data Structures
   This block focuses on data structures that support efficient pattern matching over large-scale texts, with special attention to genomic applications. We cover hash-based and k-mer indexing strategies, lexicographic tree structures, suffix trees and suffix arrays, and compressed full-text indexes based on the Burrows-Wheeler Transform.
4. Approximate String Matching
   We extend pattern matching to the approximate setting, where mismatches and indels are allowed. The block introduces distance and error models, followed by filtering and seeding techniques to reduce the search space. Index-assisted methods, sketch-based similarity estimation, verification algorithms, and chaining strategies are presented as key components of modern approximate matching algorithms and tools.
5. Pairwise Sequence Alignment
   This block addresses sequence alignment as a fundamental task in bioinformatics and genome analysis. We introduce dynamic programming techniques for computing edit distance and other alignment models under different scoring schemes, including affine gap penalties. Both classical alignment modalities and advanced algorithmic optimizations are studied, with attention to space efficiency, sparsity, and output-sensitive methods such as wavefront alignment.
6. Sequence Graphs and Pangenomics
   The course concludes with an introduction to graph-based representations of genomic variation. We discuss sequence graphs, pangenome models, and their relationship to linear references. The sequence-to-graph alignment problem is introduced, highlighting the algorithmic challenges and opportunities that arise when extending alignment techniques to graph-based genome representations.

Activities

Activity Evaluation act

Teaching methodology

Evaluation methodology

Bibliography

Basic:

• 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

Complementary:

• 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

Previous capacities