A Course on Selected Topics in Computational
University of Padova and Celera Genomics
- Mon 6/5 (2h)
- Preliminaries and Alignment Problems
DNA, amino acids and (Shotgun) sequencing.
Assembly and the Shortest Superstring Problem.
Basic Alignment. Sum-of-Pairs Multiple Sequence Alignment: Carillo
and Lipman's dynamic programming. Kececioglu et al.'s MSA
- Tue 7/5 (2h)
- Still Alignments. The Tree Alignment Problem
Gusfield's 2-approx for SP and Bafna, Lawler and Pevzner's improvements.
Heuristics for SP-Alignment. Feng and Doolittle's ``once a gap,
always a gap'' algorithm. Aligning along the min routing-cost tree.
Tree Alignment and philogenies. Sankoff's dynamic programming
algorithm. Hints to Gusfield's and Wang Lifted Alignments for
Approx guarantee and to Ravi and Kececioglu approx algorithm.
- Wed 8/5 (3h)
- End Alignments. Single Nucleotide Polymorphisms (SNPs)
Steiner Alignments: A heuristic approach to Tree alignment and
sequence alignmment. Integer Programming approaches to alignment.
Non crossing matchings. Reinert et al. I.P. algorithm for RNA alignment.
Single Nucleotide Polimorphisms. Haplotypes and genotypes.
The population haplotyping problem. Clark's rule for haplotype
inference. Gusfield's graph-theoretic model and Integer Programming
- Thu 9/5 (3h)
- SNPs problems for population and individuals
Inferring Ancestral history from haplotypes: the Haplotype Coloring
Problem and the Perfect Phylogeny SNP Haplotyping Problem
The single individual haplotyping problem. Complexity,
polynomial algorithms and heuristic/branch and bound algorithms.
- Mon 13/5 (3h)
- Genome rearrangements
Rearrangements and evolutionary distances. Inversions, Transpositions,
Translocations, Duplications and Deletions. Single chromosome
rearrangements. Breakpoints and breakpoint graph. Sorting by
Bafna and Pevzner's bound for unsigned SBR and its tightness.
Caprara, Lancia and Ng's algorithm for SBR.
- Wed 15/5 (3h)
- End rearrangements. Protein structure problems
The diameter of SBR.Cayley graphs and expected reversal distance.
Sorting by reversals-and-transpositions. Simple approx algorithm.
Signed Sorting by Reversals. Polynomial results. A linear-time
algorithm for the signed reversal distance.
Protein structures. The PDB. The folding determination problem.
The HP model and its complexity. CASP and CAFASP competitions and
- Mon 16/5 (3h)
- Protein fold comparisons
Comparing folds, and structural data bases (SCOP, DALI, ...).
Programs for structure alignments.
Contact maps and contact map alignments. An I.P. approach
to contact map overlap. Caprara and Lancia's Lagrangian
algorithm for contact map overlap. Genetic Algorithms and
local search heuristics.
© Dipartimento di Matematica - Università di Trento