To show the organization of the course that includes this module, follow this link Course organization
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).
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).
Written exam and presentation of a project.
******** CSS e script comuni siti DOL - frase 9957 ********p>