Συντάχθηκε 19-10-2026 13:20
Τόπος:
Σύνδεσμος τηλεδιάσκεψης
Έναρξη: 22/10/2026 10:30
Λήξη: 22/10/2026 11:30
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
Ηρούς Κονιδάρη
με θέμα
Κατηγοριοποίηση πρωτεϊνικών δομών με τη χρήση πολυδιάστατων γράφων οριζόντιας ορατότητας
Structural Classification of proteins based on multidimensional horizontal visibility graphs
Εξεταστική Επιτροπή
Καθηγητής Μιχαήλ Ζερβάκης (Σχολή ΗΜΜΥ, Επιβλέπων)
Καθηγητής Μιχαήλ Λαγουδάκης (Σχολή ΗΜΜΥ)
Μεταδιδακτορική Ερευνήτρια Ευφροσύνη Δούτση (ΙΠ-ΙΤΕ)
Περίληψη
Η δομική ταξινόμηση των πρωτεϊνών σε μία από τις τέσσερις κλάσεις (all-α, all-β, α/β, α+β) είναι ένα ζήτημα που έχει απασχολήσει αρκετά την επιστημονική κοινότητα στο παρελθόν, ιδιαίτερα όταν πρόκειται για πρωτεΐνες χαμηλής ομολογίας. Η συγκεκριμένη διπλωματική εργασία μελετά μια προσέγγιση για το πρόβλημα αυτό, η οποία βασίζεται σε Γράφους Ορατότητας, ακολουθεί τη μεθοδολογία των Zervou et al., υλοποιείται ανεξάρτητα σε Python και αξιολογείται συστηματικά. Η προσέγγιση αυτή συνδυάζει την Αναπαράσταση Χαοτικού Παιγνίου (Chaos Game Representation, CGR) με τους Γράφους Ορατότητας (Visibility graphs). Κάθε πρωτεΐνη περιγράφεται από την προβλεπόμενη ακολουθία δευτεροταγούς δομής της, όπου κάθε αμινοξύ αντιστοιχίζεται σε ένα από τρία δομικά στοιχεία. Αυτά είναι η έλικα (H), το coil (C) και ο κλώνος (E). Οι ακολουθίες αυτές (H/C/E) απεικονίζονται σε ένα ισόπλευρο τρίγωνο μέσω του CGR. Κάθε σημείο στο τρίγωνο κωδικοποιεί τη σειρά των προηγούμενων δομικών στοιχείων. Στη συνέχεια, κατασκευάζονται έξι Γράφοι Ορατότητας από τις σειρές συντεταγμένων x και y που προκύπτουν, ακολουθώντας τους Zervou et al. Αυτοί είναι οι VG και HVG σε μία διάσταση και οι συνδυασμοί τους AND/OR σε δύο διαστάσεις. Οι μονοδιάστατοι Γράφοι Ορατότητας αποτυπώνουν κάθε σειρά συντεταγμένων ξεχωριστά, ενώ οι δισδιάστατοι AND/OR αποτυπώνουν την κοινή τους τροχιά στο επίπεδο. Ένας Γράφος Ορατότητας μετατρέπει μια σειρά σε δίκτυο, του οποίου η τοπολογία αντανακλά τη δυναμική της σειράς (εκτεταμένες επαναλήψεις και εναλλαγές ελίκων και κλώνων). Τα μοτίβα αυτά διαφέρουν μεταξύ των δομικών κλάσεων. Τα χαρακτηριστικά της θεωρίας των γράφων μπορούν να ποσοτικοποιήσουν τα διαφορετικά μοτίβα, ανεξάρτητα από τη στοίχιση ακολουθιών. Έπειτα, οι έξι Γράφοι Ορατότητας συγκρίνονται μεταξύ τους ώστε να διαπιστωθεί ποιος τύπος φέρει την περισσότερη πληροφορία για τη δομική κλάση. Από κάθε γράφο εξάγονται εννέα τοπολογικά, φασματικά και στατιστικά χαρακτηριστικά, σύμφωνα με τους Zervou et al. Τα χαρακτηριστικά αυτά χρησιμοποιούνται για την ταξινόμηση των πρωτεϊνών, με τη βοήθεια τριών ταξινομητών: SVM (Support Vector Machines), FDA (Fisher’s Discriminant Analysis) και Random Forest. Η μεθοδολογία αξιολογείται στο σύνολο αναφοράς 25PDB (1.673 πρωτεΐνες) με διασταυρούμενη επικύρωση δέκα τμημάτων (stratified 10-fold cross-validation) επαναλαμβανόμενη 100 φορές. Η βέλτιστη συνολική ακρίβεια πολλαπλών κλάσεων (multiclass accuracy) είναι 78,2% (γράφος ορατότητας 2D-AND με SVM). Σε σύγκριση με τα δημοσιευμένα αποτελέσματα, παρατηρείται απόκλιση περίπου δέκα ποσοστιαίων μονάδων στην ακρίβεια πολλαπλών κλάσεων. Αυτή η απόκλιση οφείλεται στον διαφορετικό τρόπο υπολογισμού της συνολικής ακρίβειας. Οι δημοσιευμένες τιμές αντιστοιχούν στον μέσο όρο των ακριβειών τεσσάρων δυαδικών προβλημάτων (one-vs-rest, κάθε κλάση έναντι όλων των υπολοίπων) και όχι στην τυπική ακρίβεια πολλαπλών κλάσεων (multiclass accuracy). Αν η ακρίβεια της παρούσας εργασίας υπολογιστεί με τον ίδιο τρόπο (one-vs-rest), η διαφορά από τις δημοσιευμένες τιμές είναι κατά μέσο όρο μόλις 0,75 ποσοστιαίες μονάδες (το πολύ 2,09), σε όλους τους γράφους και για τους ταξινομητές SVM και FDA. Η ακρίβεια πολλαπλών κλάσεων διατηρείται ως το κύριο μέτρο υπολογισμού της ακρίβειας, καθώς αποτυπώνει καλύτερα το πρόβλημα των τεσσάρων κλάσεων. Τέλος, πραγματοποιείται ένα διερευνητικό πείραμα όπου ένα νευρωνικό δίκτυο γράφων (graph neural network) εφαρμόζεται απευθείας στον γράφο HVG-2D AND. Το δίκτυο αυτό επιτυγχάνει ακρίβεια πολλαπλών κλάσεων 74,1% ± 3,4 και εμφανίζει το ίδιο μοτίβο σύγχυσης κλάσεων, με τις κλάσεις α/β και α+β να συγχέονται κυρίως μεταξύ τους. Αυτό υποδηλώνει ότι τα εναπομείναντα σφάλματα προέρχονται από την ίδια την αναπαράσταση της δευτεροταγούς δομής και όχι από την επιλογή των χαρακτηριστικών που εξάγονται από τους γράφους. Η αναπαράσταση αυτή δεν αποτυπώνει τη χωρική διάταξη που διακρίνει τις δύο μικτές κλάσεις.
Abstract
The structural classification of proteins into one of four classes (all-α, all-β, α/β, α+β) has attracted the attention of the scientific community in the past, especially for proteins with low sequence similarity. This thesis presents an independent Python implementation and systematic study of a visibility-graph approach to this problem, based on the methodology of Zervou et al. It combines Chaos Game Representation (CGR) with visibility graphs. Each protein is described by its predicted secondary-structure sequence. Every residue is assigned to one of three structural elements: helix (H), coil (C) or strand (E). The predicted secondary-structure sequences (H/C/E) are mapped onto an equilateral triangle via CGR. Each point of the triangle encodes the order of the preceding structural elements. Six visibility graphs are then constructed from the resulting x and y coordinate series, following Zervou et al. (VG and HVG in one dimension, and their AND/OR combinations in two dimensions). The one-dimensional graphs capture each coordinate series separately, while the two-dimensional AND/OR graphs capture their joint trajectory in the plane. A visibility graph turns a series into a network whose topology reflects the dynamics of the series, such as long runs, repetitions and alternations of helices and strands. These patterns differ between structural classes, and graph-theoretic features can quantify them independently of sequence alignment. All six graphs are evaluated in order to compare which type carries the most information about the structural class. From each graph, nine topological, spectral and statistical features are extracted, following Zervou et al., and used to classify proteins with SVM, Fisher Discriminant Analysis and Random Forest. The pipeline is evaluated on the 25PDB benchmark (1,673 proteins) using stratified 10-fold cross-validation repeated 100 times, achieving a best multiclass overall accuracy of 78.2% (2D-AND visibility graph with SVM). In comparison with the published results, a substantial gap of roughly 10 percentage points under the multiclass definition is observed. This stems from the difference in the way overall accuracy is measured. The reported accuracies correspond to the mean of four one-vs-rest binary accuracies and not to standard multiclass accuracy. Under the one-vs-rest definition, the difference between the accuracies obtained here and the published ones is only 0.75 percentage points on average (at most 2.09) across all graphs and both SVM and FDA. Multiclass accuracy is retained as the main measure, since it reflects in a better way the four-class problem. For the next step of the present thesis, an exploratory experiment is carried out, where a graph neural network is applied directly to the HVG-2D AND graph. It reaches a multiclass accuracy of 74.1% ± 3.4 and exhibits the same class-confusion pattern, with the α/β and α+β classes predominantly confused with each other. This suggests that the remaining errors stem from the secondary-structure representation itself, rather than from the choice of handcrafted features. This representation does not capture the spatial arrangement that distinguishes the two mixed classes.
