Bioinformatics

Module 1 – Algorithms and Complexity in Bioinformatics - Introduction to algorithm analysis - Big-O, Ω, Θ notation - Efficient vs. inefficient algorithms - Tractable vs. intractable problems - NP-complete problems in bioinformatics - Algorithm design techniques: greedy, brute-force, backtracking, branch-and-bound, heuristics Skills gained: analyzing complexity, designing algorithms for biological problems Module 2 – Graphs and Molecular Networks - Data structures for graphs: adjacency lists and matrices - BFS and DFS traversal, cycle detection - Shortest paths (Dijkstra, Bellman-Ford) - Phylogenetic trees: basic definitions and use cases - Introduction to network science: protein-protein and metabolic networks Skills gained: graph traversal, modeling and analyzing biological networks Module 3 – Genome Assembly - Shotgun sequencing and next-generation technologies - The shortest common superstring problem - Overlap graphs and layout strategies - Overlap-Layout-Consensus assembly - De Bruijn graphs: construction and advantages - Concepts of contigs and scaffolding Skills gained: implementing genome assembly algorithms, understanding sequencing workflows Module 4 – Phylogenetic Tree Construction and Sequence Alignment - Multiple sequence alignment - Phylogenetic tree reconstruction using parsimony - Small and large parsimony problems - Heuristic and data-mining approaches - Alignment algorithms: Needleman-Wunsch, Smith-Waterman (brief overview) Skills gained: building and evaluating evolutionary trees from sequence data Module 5 – String Processing, Tries, and Suffix Trees - Pattern matching in biological sequences - Construction and use of tries and suffix tries - Suffix trees for pattern detection and repeat finding - Algorithms for identifying unique and repeated substrings Skills gained: efficient text processing for genomic applications Module 6 – Probability Theory and Statistical Modeling - Basic discrete probability, independence, distributions - Random variables and expected values - Birthday paradox and its applications - Modeling the occurrence of patterns in random sequences Skills gained: applying probabilistic reasoning in biological data contexts Module 7 – Markov Chains and Hidden Markov Models (HMMs) - Markov chains: transition matrices, long-term behavior - The “Fair Bet Casino” model - Hidden Markov Models: definition and structure - Evaluation, decoding, and learning problems - Applications to CpG island detection and gene prediction Skills gained: statistical modeling of sequence data, working with hidden states Module 8 – Practical Programming and Cloud Computing - Implementing algorithms in Python - Using advanced data structures (dictionaries, heaps, graphs) - Introduction to AWS: running scripts on EC2, handling large-scale datasets - Case studies and project work Skills gained: writing bioinformatics tools, using cloud resources effectively Assessment: 3 Homework Assignments**: blending theory, coding, and real bioinformatics tasks

To fully benefit from the course, students should have prior knowledge and skills in the following areas: 1. Programming Fundamentals - Proficiency in Python (data structures, control flow, file handling) - Ability to write, debug, and analyze basic scripts 2. Discrete Mathematics - Understanding of sets, relations, functions, logic, and combinatorics - Basic graph theory (trees, paths, connectivity) 3. Algorithms and Data Structures - Sorting and searching algorithms - Basic algorithm design strategies (greedy, divide-and-conquer) - Notions of computational complexity and Big-O notation 4. Probability and Statistics - Elementary probability theory (events, conditional probability, independence) - Random variables and expectation 5. Molecular Biology and Bioinformatics Basics - DNA, RNA, and protein structures - Familiarity with biological sequence data (FASTA format, genome structure) - Basic knowledge of sequence alignment and phylogenetic trees 6. Linux and Command Line Usage (recommended but not required) - Navigating directories, running Python scripts, working with files 7. Cloud Computing Fundamentals (optional but useful) - Basic understanding of cloud platforms such as AWS - Using virtual machines or compute instances

NEIL C. JONES AND PAVEL A. PEVZNER: An Introduction to Bioinformatics Algorithms. A Bradford Book, The MIT Press, Cambridge, Massachusetts, 2004. THOMAS H. CORMEN, CHARLES E. LEISERSON, RONALD L. RIVEST AND CLIFFORD STEIN: INTRODUCTION TO ALGORITHMS. The MIT Press, Cambridge, Massachusetts, 2009. JON KLEINBERG AND EVA TARDOS. Algorithm Design. Pearson, 2009. Albert-László Barabási, Network Science. Cambridge University Press

The Complex Biomolecular Networks course is conducted through weekly in-person lectures held twice per week.

Student evaluation in Complex Biomolecular Networks is based on a balanced combination of theoretical understanding, algorithmic design, and practical programming skills. The assessment includes three homework assignments distributed throughout the semester, each designed to reinforce key concepts through both written problems and Python implementations. These assignments contribute significantly to the final grade and emphasize individual effort and comprehension. In addition, students will sit for a final exam. Active participation and consistent engagement with programming tasks and AWS-based exercises are essential to succeed in the course.

The Complex Biomolecular Networks course is conducted through weekly in-person lectures held twice per week. The course combines theoretical instruction with hands-on programming exercises in Python, gradually building from fundamental algorithmic principles to advanced applications in bioinformatics. Lectures are structured to introduce core concepts (e.g., graph algorithms, sequence analysis, probabilistic models), which are then reinforced through worked examples, problem-solving sessions, and guided discussions. Practical aspects, such as implementing algorithms and working with cloud-based resources (AWS), are integrated into the teaching and supported through regular assignments. Students are expected to actively participate, bring their laptops to class for in-lecture coding activities, and progressively develop their own toolkit for solving real-world computational biology problems.