Algorithms and programming languages for bioinformatics - ALGORITMI PER BIOINFORMATICA (2011/2012)

Course not running

Course code
4S000525
Name of lecturer
Zsuzsanna Liptak
Number of ECTS credits allocated
6
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Location
VERONA
Period
II semestre dal Mar 1, 2012 al Jun 15, 2012.
Web page
http://profs.sci.univr.it/~liptak/ALBioinfo

To show the organization of the course that includes this module, follow this link * Course organization

Lesson timetable

Learning outcomes

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

Syllabus

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 (sketch); Formalism on strings/sequences; Scoring matrices: PAM (computation, application); Heuristics for sequence alignment: dotplots, q-grams, FASTA, BLAST;

STRING SIMILARITY AND DISTANCE

String similarity and distance: percent similarity, edit distance, Hamming distance, connection between edit distance and alignment score;

ALGORITHM ANALYSIS

Introduction to algorithm analysis: time and storage space analysis; notation for complexity analysis: Big-Oh-notation, growth of functions;

PHYLOGENETICS

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

STATISTICS

Some basic statistics (hypothesis testing, P-values, type I and II errors, descriptive statistics).

Assessment methods and criteria

Written exam: 50%, and presentation of a project (talk with digital slides): 50%
The written exam can be taken in two parts (midterm and final), in which case both have to be passed; or in one (complete final exam).

Share