Algorithms for computational biology (2015/2016)

Course code
4S003660
Name of lecturer
Zsuzsanna Liptak
Coordinator
Zsuzsanna Liptak
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
English
Period
I semestre dal Oct 1, 2015 al Jan 29, 2016.
Web page
http://profs.scienze.univr.it/~liptak/ACB/

Lesson timetable

I semestre
Day Time Type Place Note
Thursday 10:30 AM - 12:30 PM lesson Lecture Hall L  
Friday 1:30 PM - 4:30 PM lesson Lecture Hall H  
Friday 4:30 PM - 5:30 PM lesson Lecture Hall H from Oct 30, 2015  to Jan 29, 2016

Learning outcomes

1. to learn about some basic problems and algorithms behind common bioinformatics applications (sequence alignment, sequence similarity, phylogenetics), and 2. to get an idea of some basic computational issues (problem specification, efficiency of algorithms, limitations).

Syllabus

ALGORITHM ANALYSIS

Introduction to algorithm analysis: running time and storage space analysis; notation for complexity analysis: Big-Oh-notation, growth of functions; formalism on strings/sequences; basic combinatorics on strings;

SEQUENCE ALIGNMENT

Applications; Pairwise sequence alignment: Exhaustive search, Dynamic programming (DP) algorithm of Needleman-Wunsch (global alignment), DP algorithm of Smith-Waterman (local alignment), other variants; multiple sequence alignment: DP algorithm and heuristics; Scoring matrices: PAM (computation, application); Heuristics for sequence alignment and database search: BLAST; string distance and similarity, edit distance;

PHYLOGENETICS

Introduction to graphs and trees; number of phylogenetic trees; distance-based data: algorithm UPGMA; character-based data: Perfect Phylogeny (PP), Small parsimony: Fitch' algorithm; Large parsimony: heuristics.

Assessment methods and criteria

Written exam, followed by oral exam.

STUDENT MODULE EVALUATION - 2015/2016