# Algorithms for computational biology (2015/2016)

Course code
4S003660
Name of lecturer
Zsuzsanna Liptak
Coordinator
Zsuzsanna Liptak
Number of ECTS credits allocated
6
INF/01 - INFORMATICS
Language of instruction
English
Location
VERONA
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.