Complex Biomolecular Networks

Third Year / First Semester Course L-2 - 1049270

(A. A. 2024/2025)

Syllabus

The main objective of the course Complex Biomolecular Networks is to provide students with an overview of algorithmic methods designed for the analysis of genomic sequences. A key goal is to develop skills in algorithm design while emphasizing the role of algorithms in bioinformatics, particularly in complexity analysis and performance evaluation. The course explores both theoretical and combinatorial aspects, alongside practical applications such as whole genome sequencing, sequence alignment, pattern searching in biological sequences, and the inference of repeated patterns. Additionally, it introduces fundamental concepts and tools for the analysis of complex networks, enabling students to apply network science principles to biological networks and understand underlying molecular processes.

The course aims to deepen students' understanding of sequence- and structure-based computational methods for analyzing biological sequences beyond basic pairwise alignment. Topics include multiple sequence alignment, phylogenetic tree reconstruction, sequence motif detection, the use of hidden Markov models for sequence analysis, and gene prediction. Structure-based methods focus on predicting RNA and protein secondary structures, as well as their structural alignment. While the course is centered on algorithmic principles and methods, it also includes hands-on applications of relevant tools and databases, equipping students with practical skills for computational analysis in bioinformatics.

We will work with Python and how to write a computer program encoding a given algorithm. We will work with Amazon's AWS and how to use cloud resources to efficiently execute our python programs on large datasets.

Location

All classes take place in Classroom Psicologia II, Fisiologia Generale e Antropologia Farmacia e Medicina (CU026, E01PS1L084).

Time Schedule

  • Tuesday 08:30-11:00
  • Thursday 08:30-11:00:

Contact & Discussions

All announcements and discussions will be carried out through Google Classroom lbnrx37

ASSIGNMENTS

A total of three assignments will be handed over. These assignments are done by each student individually. Clearly you should discuss with other students of the course about the assignments. However, you must understand well your solutions and the final writeup must be yours and written in isolation. In addition, even though you may discuss about how you could implement an algorithm, what type of libraries to use, and so on, the final code must be yours. You may also consult the internet for information, as long as it does not reveal the solution. If a question asks you to design and implement an algorithm for a problem, it's fine if you find information about how to resolve a problem with character encoding, for example, but it is not fine if you search for the code or the algorithm for the problem you are being asked. For the projects, you can talk with other students of the course about questions on the programming language, libraries, some API issue, and so on, but both the solutions and the programming must be yours. If we find out that you have violated the policy and you have copied in any way you will automatically fail. If you have any doubts about whether something is allowed or not, ask the instructor.

Lecture Material

  • Lecture 1: Asymptotic Analysis
  • Lecture 2: Computational Complexity
  • Lecture 3: Branch and Bound
  • Lecture 4: Biological Networks
  • Lecture 5: Graph Traversal Algorithms
  • Lecture 6: Graph Traversal Algorithms
  • Lecture 7: Single-source Shortest Paths
  • Lecture 8: Single-source Shortest Paths
  • Lecture 9: Phylogenetic Analysis
  • Lecture 10: Small Parsimony Problem
  • Lecture 11: Large Parsimony Problem
  • Lecture 12: Data Mining
  • Lecture 13: DNA Sequencing
  • Lecture 14: DNA Assembly
  • Lecture 15: DNA Assembly & De Bruijn Graphs
  • Lecture 16: DNA Assembly & Suffix Trees
  • Lecture 17: DNA Assembly in the real world
  • Lecture 18: Probabilistic Analysis
  • Lecture 19: Markov chains and Sequence Evolution
  • Lecture 20: Hidden Markov Models
  • Lecture 21: Hidden Markov Models

References

  1. NEIL C. JONES AND PAVEL A. PEVZNER: An Introduction to Bioinformatics Algorithms. A Bradford Book, The MIT Press, Cambridge, Massachusetts, 2004.
  2. THOMAS H. CORMEN, CHARLES E. LEISERSON, RONALD L. RIVEST AND CLIFFORD STEIN: INTRODUCTION TO ALGORITHMS.

The MIT Press, Cambridge, Massachusetts, 2009.

  1. JON KLEINBERG AND EVA TARDOS. Algorithm Design. Pearson, 2009.