Πανεπιστήμιο Αθηνών, Tμήμα Πληροφορικής & Τηλεπικοινωνιών

Αλγόριθμοι στη Δομική Βιοπληροφορική:
Αλγεβρικoί και Γεωμετρικoί Αλγόριθμοι
Καθηγ. Ι. Εμίρης

ΠΜΣ ΤΠΙΒ, κατεύθυνση Βιοπληροφορικής
ΜΠΛΑ Π03Ζ
ΠΜΣ 507(ε): Υπολογιστικές μέθοδοι στις επιστήμες
ΘΠ16: Ειδικά Θέματα Θεωρητικής Πληροφορικής

Εαρινό εξάμηνο 2008, Τρίτη 4-7, αίθουσα E'

3d structure

ΕΒΔΟΜΑΔΑ
 ΥΛΗ ΑΡΘΡΑ
0. 4/3
Εισαγωγή
Οργάνωση μαθήματος. Επισκόπηση και περιοχές του γνωστικού αντικειμένου. Aλγόριθμοι, ασυμπτωτική πολυπλοκότητα. DNA, RNA και πρωτεϊνες (pdf). Πρωτοταγής, δευτεροταγής, τριτοταγής, τεταρτοταγής δομή. Protein Data Bank.

1-1b. 4-5/3
Δυναμικός Προγραμματισμός
Αλληλουχίες και βαθμολόγηση ομοιότητας. Kαθολική (Needleman-Wunch) και τοπική στοίχιση (Smith-Waterman), υπολογισμός βέλτιστης στοίχισης. Στοίχιση με κενά. Δυναμικός προγραμματισμός σε γραμμικό χώρο [DEKM,ch.2] (pdf)

2. 11/3
 Δευτεροταγής δομή RNA [DEKM,ch.10]. Προσεγγιστικές μέθοδοι BLAST, FASTA. Εφαρμογή στην 3Δ δομή πρωτεϊνών.
 Άρθρα ΔΠ No 1-2
3. 18/3
Γεωμετρία  Αποστάσεων
Γεωμετρία των Αποστάσεων, πίνακες αποστάσεων. Βελτίωση περιορισμών. Συνθήκες και Πολυπλοκότητα εμβύθισης σε Ευκλείδειο χώρο [X.Κοναξής (pdf)]
4-6. [25/3] 1/4, 8/4
 Γεωμετρία των Αποστάσεων, πίνακες Cayley-Menger, Θετικά (ημι)ορισμένοι πίνακες. Γραμμική άλγεβρα για εμβύθιση.
--
 Χορδικοί Γράφοι. Τριγωνική ανισότητα και ελάχιστα μονοπάτια, Τετραεδρική ανισότητα (pdf).
--
Βελτίωση περιορισμών και εμβύθιση [X.Φραγκουδάκης (pdf)]
Εφαρμογή σε στοίχιση δομών (struct.alignment)
 Άρθρα γεωμετρίας αποστάσεων No 1-2
--
Άρθρα γεωμετρίας αποστάσεων No 3-4
7-8. 15/4 - 6/5
Γεωμετρικοί αλγόριθμοι 		Διάγραμμα Voronoi [de Berg et al]: ορισμοί, ιδιότητες, αλγόριθμοι, πολυπλοκότητα. Tριγωνοποίηση Delaunay.
--
Tριγωνοποίηση Delaunay:  ιδιότητες, αλγόριθμοι. α-σχήματα και υπολογισμός τους [Fischer]. Eφαρμογή στην αναπαράσταση μοριακής επιφάνειας για πρόσδεση μορίων (docking).
--
Oμιλία Γιάννη Βαλαβάνη
 Άρθρα Interfaces No 1-2.
--
Assignment 1 (due Tu. 6 May) Solution
--
άρθρα 1-2: α-Σχήματα / Γεωμετρικοί αλγόριθμοι
9. 13/5
10. 20/5
Κινηματική
Χημικοί δεσμοί και Μοριακή δομή. Πίνακες Ευκλείδειων μετασχηματισμών. Μοντελοποίηση μοριακής γεωμετρίας μέσω αλγεβρικών συστημάτων
--
Kινηματική [X.Συρσελούδης, pdf].
Τριτοταγής δομή από δεδομένα NMR, RDC [Σ.Πάντος. pdf]
Αλγεβρικοί αλγόριθμοι [X.Koναξής, pdf]
 2 άρθρα Κινηματικής και Τριτοταγούς δομής
--
Kατάλογος απαλλακτικών
[11. 27/5]
12. 3/6
 Kινηματική (pdf). Στοίχιση δομών, (least)RMSD (pdf)
Xώροι διαμορφώσεων (C-space). Διάγραμμα Voronoi στον χώρο διαμορφώσεων.
--
Oμιλία Marco Antoniotti
 3 άρθρα Κινηματικής και Τριτοταγούς δομής
13. 10/6
Αλγεβρικοί αλγόριθμοι
Μελέτη πολυωνυμικών συστημάτων. Καλώς ορισμένα αλγεβρικά συστήματα. Mέθοδοι επίλυσης αλγεβρικών συστημάτων. Αναγωγή σε πρόβλημα πινάκων και μέθοδος της απαλοίφουσας (resultant) (pdf)
---
Αλγεβρικοί αλγόριθμοι για διαμορφώσεις και πρόσδεση (μοντελοποίηση, επίλυση, εφαρμογές) (pdf) [E.Φριτζίλας], Quaternions
 2 άρθρα Τριτοταγούς δομής
--
Assignment 2 (due Wed.June 25). solution
Tue July 1st
11am - 2pm
 Final exam: 10-min presentations
 FINAL GRADES

Σημειώσεις: Tου διδάσκοντα στα ελληνικά (pdf).
Αξιολόγηση εδώ.
Bαθμολογία (προκαταρκτικά) [%]:
Ασκήσεις (25-30), 2 παρουσιάσεις (35-40), απαλλακτική (35-40).

Παρουσίαση άρθρου. Καθένας παραδίδει αρχείο παρουσίασης (10-20 διαφάνειες), στην συνέχεια παρουσιάζει προφορικά (20-25 λεπτά). Kατάλογος ΘΕΜΑΤΩΝ (Ορισμένοι σύνδεσμοι λειτουργούν από υπολογιστή στο ΕΚΠΑ)
Απαλλακτική εργασία. Καθένας: Διαβάζει 1-2 εργασίες, υλοποιεί / βελτιώνει τον αντίστοιχο αλγόριθμο, ή συγκρίνει υπάρχοντα λογισμικά σε μοριακά δεδομένα. Παραδίδει περίληψη δουλειάς, περιγραφή λογισμικού, πειραματικά αποτελέσματα, συμπεράσματα (4-5 σελίδες). Παρουσιάζει τα παραπάνω προφορικά (20 λεπτά) την ημέρα της τελικής εξέτασης. Οι εργασίες μπορούν να γίνουν σε ομάδες των 2 ατόμων. Kατάλογος ΘΕΜΑΤΩΝ
Bιβλία/Υλικό
  • Lawrence Hunter. Molecular Biology for Computer Scientists. http://compbio.uchsc.edu/Hunter/01-Hunter.pdf
  • Ιntro to Protein science, Architecture, function and genomics. A. Lesk, Oxford U. Press [Πληροφορική]
  • Intro to protein architecture: the structural biology of proteins. A. Lesk. Oxford U. Press, 2001 [Πληροφορική].
  • Molecular Modelling: Principles and Applications. A.R. Leach. 2001 [Πληροφορική]
  • Bioinformatics: Sequence and genome analysis, D.W. Mount.
  • Biological sequence analysis, Durbin, Eddy, Krogh and Mitchison, Cambridge, 1998 [διδάσκων].
  • Intro to Bioinformatics algorithms (Comp. Mo. Bio). Jones & Pevzner. [Πληροφορική]
  • Kεφάλαιο βιβλίου [Εdelsbrunner]
  • Δημοσιεύσεις στα συνέδρια της ACM (RECOMB, SoCG) βρίσκονται στην βιβλιοθήκη της ACM (από υπολογιστή του ΕΚΠΑ).
    • Ι. Eμίρης
    Εικόνα: Η γεωμετρία των καταλοίπων 24-28 στην ubiquitin [Σ.Πάντος]