An Introduction To Sequence Comparison and Database Search

Bergen University, January 2018

Cedric Notredame


An intermediate level course on algorithms in bioinformatics. We will use it to explain common concepts in sequence analysis, starting from the biological relevance of sequence alignment and making our way through the most commonly used algorithms, including Needleman and Wunsch, Smith and Waterman for pairwise alignments, BLAST for database searches, Nussinov for RNA folding and the progressive multiple alignment. We will aslo provide an introduction to Hidden Markov Modelling through the occasionally dishonest casino exemple. The practicals will be in Python and will involve driving the students through an implementation of these algorithms. The biobliography is given by order of importance.


Practicals will be in python 2.7. They will involve adapting existing scripts rather than programming from scratch. For this reason, students with no practical knowledge of python but with a good grasp of programming languages like Perl, C or JAVA should manage reasonnably well. Students are expected to bring their own lap-top and advised to have a LINUX boot though Virtual MAchine support will be provided.


Using the information and the code provided in the practical 4.1 assemble a multiple sequence aligner. Report on this task and on the combination of the various algorithmic components. Report on the stability of this aligner, especially with respect to the sequence input order. Note: you can use the tcoffee package to compare your alignment with the option t_coffee -other_pg aln_compare

Send your Questions to:

1.1BULECTUREPairwise comparisons in an evolutionary contextL
1.2BULECTUREIntroduction to Dynamic ProgrammingL
1.1 BU PRACTICALSParsing Biological FilesP
1.2 BU PRACTICALSComputing Substitution MatricesP
2.1BULECTUREIntroduction to Dynamic ProgrammingL
2.2BULECTURERNA Folding Predictions L
2.1 BUPRACTICALSIntroduction to Dynamic ProgrammingP
2.2 BUPRACTICALSIntroduction to Dynamic ProgrammingP
3.1BULECTUREBlast AlgorithmL
3.2BULECTUREMSA IntroductionL
3.1 BUPRACTICALSNussinov AlgorithmP
4.2BULECTUREHMM Introduction IL
4.1 BUPRACTICALSImplementing an MSA AlgorithmP
5.1BULECTUREHMM Introduction IIL


1. Algorithms: Durbin et al., Biological Sequence Analysis, 1999, Oxford Press

2. Algorithms: Python for Biologists: A complete programming course for beginners, Martin Jones,2013 , Createspace Independent Publishing Platform

3. Evolution: Pathy, Protein Evolution, 2007, Blackwell

This Entire Course Was Automatically Generated Using BED, the Bioinformatics Exercise Database. BED is a freeware available on request Cedric Notredame