Bioinformatics

Lecture notes :

• link to download: Complete lecture slides (slides only , no video) (large file: 180 Mb)

Videos (and Implementation examples):

To facilitate the comprehension, the videos will follow closely the slide content; lectures are partitioned in 15-20 minute videos.

Implementations: short programs useful to check data structures, loops, etc (not examinable); Note below could be useful for further details

WIP means work in progress

Weekly availability to meet students and supervisors (send email to pl219). I am happy to send more materials
on some topics (without changing the level of difficulty of exam questions).

• Lecture1 (Video): Introduction and Biological concepts (NON EXAMINABLE) (large file: 10 Mb)
• Data Repositories (with link to human reference genome)
  
• Genome sequence of Sars-cov2 (NC_045512.2)_ non examinable
• Biopython (tutorial)- non examinable

• Lecture1 (Video): Longest common subsequence (large file: 10 Mb)
• Implementation: longest common subsequence.py

• Lecture2 (Video): Global and Local alignment (large file: 10 Mb)
• Implementation: Needleman-Wunsch alignment.py
• Implementation: Smith-Waterman alignment.py
• Implementation: Example pairwise alignment.py
• Implementation: Affine Gap.py (from Rosalind.info)
• Implementation: Pam250.py
• Note on affine gaps (P Pevzner)
• Note on affine gaps (R. Durbin)

• Lecture2 (Video): Linear Time alignment (Hirschberg) (large file: 10 Mb)

• Notes on Hirschberg algorithm from Gusfield
• Implementation: AlignTwoStringInLinearSpace.py

• Lecture2 : Four Russians speedup; RNA folding (large file: 10 Mb)
• Notes on Four Russians speedup from Gusfield
• Notes on Four Russians speedup from Michal Ziv-Ukelson
• Implementation: RNA_Nussinov.py
• Implementation: RNA_Four Russians cpp
• Implementation: RNA_Four Russians hpp
• Implementation: RNA_Four Russians main cpp

• Lecture3 (Video): Building trees (large file: 10 Mb)
• Note: relationship  between species and trees (NON EXAMINABLE)
  

• Lecture3 (Video): Additive Phylogeny (large file: 10 Mb)
• Implementation: additivephylogeny.py
• Implementation: distance_matrix.py

• Lecture3 (Video): UPGMA and Neighbor-Joining (large file: 10 Mb)
• Implementation: upgma.py
• Implementation: squared_error_distortion.py
• Implementation: neighbor_joining.py
• Implementation: limb_length.py

• Lecture3 (Video): Small and Large Parsimony ; trees and multialignment(large file:10 Mb)
• Implementation: parsimony.py
• Implementation: clustal.py

• Lecture4 (Video): Genome Sequencing (large file: 10 Mb)
• Implementation: reads example

• (Video): DeBruijn Graph (large file: 10 Mb)
• Implementation: DeBruijn.py
• Implementation: example.py

• Lecture4 (Video): DeBruijn Pairs  (large file: 10 Mb)

• Lecture5 (Video): Lloyd algorithm for clustering (large file: 10 Mb)
• Implementation: Lloyd.py
• Implementation:farthest_first_travers.py
• Implementation: hierarchical_clustering.py

• Lecture5 (Video): Expectation-Maximisation (large file: 10 Mb)
• Implementation:soft_k-means_clustering.py

• Lecture5 (Video): Markov Clustering Algorithm (large file: 10 Mb)
• Implementation: mcl_clustering.py

• Lecture6 (Video): Genome Assemble (large file: 10 Mb)

• Lecture6 (Video): Burrows-Wheeler Transform (large file: 10 Mb)
• Note on Burrows-Wheeler Transform, FM index, suffix arrays
• Implementation: Burrows-Wheeler Transform.py
• Implementation: Burrows-Wheeler Transform with example.py
• Implementation: trie.py
• Implementation: suffix tree.py

• Lecture7 (Video): Hidden Markov Models: Viterbi (large file: 10 Mb)
• Implementation: Viterbi_algorithm.py
• Implementation: Viterbi_learning.py

• Lecture7 (Video): Hidden Markov Models: Forward and Backward (large file: 10 Mb)
• • Implementation: Forward and Backward.py
  • Implementation: TMHMM.py Transmembrane protein segments prediction
• Notes on protein classification using HMM (Non examinable)

• Lecture8 (Video): How to compute with DNA (large file: 10 Mb)

• Lecture9 (Video): How to use DNA as memory storage (large file: 10 Mb)

• Lecture10 (Video): How to simulate genetic and protein reaction networks: Doob-Gillespie (large file: 17 Mb)
• Implementation: Gillespie.m
• Gillespy (implements several variants)


• Lecture 11 Revision (Video) , Textbook reference , Revision note 1 , Revision note 2 , Revision note 3 (large files: 10 Mb)
  
  
• Lecture12 (Video): Example Class (I am happy to organise online example class with students) (large file: 10 Mb)
Link to Bioinformatics Example class slides only
• Guideline exam answers (main take home: questions are enough general so there is always something to write)
• Past exam questions



• Note on Privacy&Ethics using bioinformatics for sensitive data analysis
• Ten rules to read a scientific paper
• What to stress in a Bioinformatics job interview


• Additional References: original papers (PDF) (non necessary for the exams!)


• Algorithms for the Longest Common Subsequence Problem by Hirschberg
• Four Russians implementation on string edit problem by Masek and Paterson
• Computational prediction of eukaryotic protein-coding genes by M. Zhang
• Algorithms_for_Loop_Matching by R. Nussinov et al
• A Block-sorting Lossless Data Compression Algorithm by Michael Burrows and David Wheeler
• Opportunistic data structures with applications by Paolo Ferragina and Giovanni Manzini
• Suffix Arrays: A New Method for On-Line String Searches by Manber and Myers
• Adleman original paper
• DNA storage: random access
• DNA storage: review paper
• Daniel Gillespie paper (1976)
• Daniel Gillespie paper (1977)