- / -

Η μελέτη των βιολογικών συστημάτων στα διαφορετικά επίπεδα οργάνωσης του κυττάρου είναι ένας τομέας που αναδύεται ταχύτατα στην περιοχή της υπολογιστικής βιολογίας. Η πλειοψηφία των ερευνών σε αυτό τον τομέα έχει επικεντρωθεί στον διαχωρισμό των γονιδίων σε βιολογικά μονοπάτια ή διεργασίες. Το επόμενο βήμα στην κατανόηση του κυττάρου στο συστημικό του επίπεδο είναι ο καθορισμός του τρόπου με τον οποίο οι συγκεκριμένες κυτταρικές διεργασίες λειτουργούν μαζί για να επιτελέσουν τις κυτταρικές λειτουργίες. Βασικός σκοπός της παρούσας διπλωματικής εργασίας είναι η πρόβλεψη αλληλεπιδράσεων διαφόρων ειδών οι οποίες λαμβάνουν μέρος στα διαφορετικά επίπεδα του κυττάρου καθώς και η διερεύνηση του τρόπου με τον οποίο αυτές οι αλληλεπιδράσεις συνεργάζονται μεταξύ τους έτσι ώστε να επιτελέσουν τις κυτταρικές λειτουργίες. Στο χαμηλότερο επίπεδο του κυττάρου υπάρχουν οι φυσικές αλληλεπιδράσεις οι οποίες ισοδυναμούν με σύνδεση των πρωτεϊνών (ή μιας πρωτεΐνης και ενός DNA μορίου) στον 3-διάστατο χώρο. Η σύνδεση αυτή μπορεί να έχει διάφορα αποτελέσματα, όπως η μεταφορά ενός βιοσήματος ή η δημιουργία ενός νέου βιομορίου. Σε ένα ανώτερο επίπεδο από τις φυσικές αλληλεπιδράσεις, πραγματοποιούνται οι λειτουργικές αλληλεπιδράσεις οι οποίες μπορούν σε γενικές γραμμές να κατηγοριοποιηθούν σε σειριακές λειτουργικές αλληλεπιδράσεις (δίκτυα ρυθμιστικών αλληλεπιδράσεων), παράλληλες λειτουργικές αλληλεπιδράσεις όπως για παράδειγμα η συνθετική θνησιμότητα (γενετικές αλληλεπιδράσεις) και συνεργατικές λειτουργικές αλληλεπιδράσεις, όπως για παράδειγμα τα πρωτεϊνικά σύμπλοκα. Οι βιολογικές διεργασίες οι οποίες δραστηριοποιούνται στο ανώτατο επίπεδο του κυττάρου είναι στην πραγματικότητα ομάδες πρωτεϊνών και γονιδίων τα οποία λειτουργούν συνεργατικά. Οι αλληλεπιδράσεις μεταξύ των βιολογικών διεργασιών είναι οι υψηλότερου κυτταρικού επιπέδου αλληλεπιδράσεις τις οποίες θα μπορούσαμε να ανιχνεύσουμε. Η ανίχνευση των παραπάνω διαφορετικών ειδών αλληλεπιδράσεων καθώς και η εννοιολογική σύνδεσή τους αποτελεί το αντικείμενο μελέτης της παρούσας διπλωματικής εργασίας. Η αναγκαία πληροφορία για να οδηγηθούμε στην πρόβλεψη αλληλεπιδράσεων του ανώτερου επιπέδου του κυττάρου είναι οι χαμηλού επιπέδου (physical) πρωτεϊνικές αλληλεπιδράσεις. Πολλές υπολογιστικές μέθοδοι έχουν εφαρμοστεί μέχρι στιγμής στο πρόβλημα της πρόβλεψης πρωτεϊνικών αλληλεπιδράσεων, οι οποίες όμως αποτυγχάνουν στην ταυτόχρονη επίτευξη καλής απόδοσης και ερμηνευσιμότητας. Στα πλαίσια της διπλωματικής εργασίας αναλύεται το πρόβλημα της πρόβλεψης πρωτεϊνικών αλληλεπιδράσεων. Περιγράφονται οι πιο πρόσφατες πειραματικές και υπολογιστικές μέθοδοι για την ανίχνευση τους. Αναλύονται οι διαφορές τους, τα πλεονεκτήματα και τα μειονεκτήματά τους και επιπλέον γίνεται μία προσπάθεια καταγραφής των στοιχείων που τις περιορίζουν και προτείνονται τρόποι για την μελλοντική εξέλιξη και βελτίωσή τους. Στην συνέχεια μελετάται ο τρόπος με τον οποίο η τοπολογία των δικτύων πρωτεϊνικών αλληλεπιδράσεων επηρεάζει τις λειτουργικές αλληλεπιδράσεις που εμφανίζονται στο εσωτερικό του κυττάρου, όπως για παράδειγμα τις ρυθμιστικές (regulatory) και τις επιστατικές (genetic) αλληλεπιδράσεις. Δημιουργείται ένα σταθμισμένο δίκτυο το οποίο περιέχει πληροφορία για τις αλληλεπιδράσεις μεταξύ των πρωτεϊνών στο φυσικό επίπεδο (physical interactions). Η εκμετάλλευση της τοπολογίας του δικτύου φυσικών αλληλεπιδράσεων γίνεται μέσω τεχνικών διάχυσης πυρήνων (kernel diffusion). Τροποποιώντας τον βαθμό της διάχυσης (degree of diffusion), δημιουργούνται τα προφιλ διάχυσης (diffusion profiles). Στην συνέχεια, αυτά τα προφίλ χρησιμοποιούνται προκειμένου να χαρακτηρίσουν τις τοπολογίες που συνδέουν τις πρωτεΐνες πάνω στο δίκτυο φυσικών αλληλεπιδράσεων. Επίσης τα προφίλ διάχυσης, αποδεικνύονται εξαιρετικά χρήσιμα εργαλεία στην βελτίωση της απόδοσης των αλγορίθμων πρόβλεψης λειτουργικών αλληλεπιδράσεων. Στην συνέχεια οι πρωτεϊνικές αλληλεπιδράσεις χρησιμοποιούνται εκ νέου προκειμένου να προβλεφθούν εξαρτήσεις σε ένα επίπεδο υψηλότερα των λειτουργικών αλληλεπιδράσεων και συγκεκριμένα μεταξύ βιολογικών διεργασιών όπως αυτές περιγράφονται στην βάση δεδομένων Gene Ontology. Η κλασσική προσέγγιση στην μελέτη πολύπλοκων βιολογικών δικτύων βασίζεται στην ταυτοποίηση αλληλεπιδράσεων μεταξύ εσωτερικών συστατικών μεταβολικών ή σηματιδικών μονοπατιών. Επιπλέον, γνωρίζουμε σήμερα πολύ λίγα πράγματα για τις αλληλεπιδράσεις μεταξύ βιολογικών συστημάτων ανώτερης τάξης, όπως είναι τα βιολογικά μονοπάτια και οι βιολογικές διεργασίες. Στα πλαίσια της διπλωματικής εργασίας προτείνεται μια μεθοδολογία για την εύρεση αλληλεπιδράσεων μεταξύ βιολογικών διεργασιών αναλύοντας σταθμισμένες και μη σταθμισμένες πρωτεϊνικές αλληλεπιδράσεις. Βασική απόρροια της διπλωματικής εργασίας είναι οι αλληλεπιδράσεις μεταξύ βιολογικών διεργασιών που προέκυψαν και μέσω των οποίων δημιουργείται ένα νεο είδος δικτύου, το δίκτυο αλληλεπιδράσεων μεταξύ βιολογικών διεργασιών. Διάφορες βάσεις δεδομένων έχουν σχεδιαστεί για την αποθήκευση πληροφορίας σχετικής με τις πειραματικά και υπολογιστικά ταυτοποιημένες ανθρώπινες πρωτεϊνικές αλληλεπιδράσεις. Ωστόσο, αυτές οι βάσεις δεδομένων περιέχουν πολλές λανθασμένα θετικές αλληλεπιδράσεις, έχουν χαμηλή κάλυψη και μόνο λίγες από αυτές ενσωματώνουν πληροφορία από διάφορες πηγές. Για την αποφυγή των παραπάνω προβλημάτων, έχει σχεδιαστεί η βάση δεδομένων ΗΙΝΤ-ΚΒ (http://150.140.142.24:84) η οποία είναι μία βάση γνώσης που ενσωματώνει δεδομένα από διάφορες πηγές, παρέχει ένα φιλικό περιβάλλον προς τον χρήστη για την ανάκτησή τους, υπολογίζει ένα σύνολο χαρακτηριστικών και ένα σκορ εμπιστοσύνης για κάθε πιθανή πρωτεϊνική αλληλεπίδραση. Το σκορ εμπιστοσύνης είναι βασικό για το φιλτράρισμα των λανθασμένα θετικών αλληλεπιδράσεων οι οποίες είναι παρούσες σε διάφορες υπάρχουσες βάσεις δεδομένων. Για το σκοπό αυτό δημιουργήθηκε μία νέα υβριδική μεθοδολογία μηχανικής μάθησης, η οποία ονομάζεται Μαθηματική Μοντελοποίηση Εξελικτικού Κάλμαν (ΜΜΕΚ) για την επίτευξη μιας ακριβούς και ερμηνεύσιμης διαδικασίας ανάθεσης βαρών στις πρωτεϊνικές αλληλεπιδράσεις. Τα πειραματικά αποτελέσματα καταδεικνύουν ότι η συγκεκριμένη μέθοδος υπερτερεί σε σχέση με τις πιο γνωστές μεθόδους πρόβλεψης πρωτεϊνικών αλληλεπιδράσεων. Τα αποτελέσματα της διπλωματικής εργασίας φιλοδοξείται να συμβάλλουν στην πρόβλεψη νέων πιθανών αλληλεπιδράσεων του χαμηλού και του υψηλού κυτταρικού επιπέδου του ανθρώπινου οργανισμού και του οργανισμού του Ζακχαρομήκυτα (S. cerevisiae). Επιπλέον, μπορούν να χρησιμοποιηθούν για την κατανόηση των ανώτερων επιπέδων οργάνωσης του κυττάρου σαν ένα ενιαίο σύστημα. Τέλος, μία ακόμη σημαντική απόρροια που προκύπτει από την ανάλυση που παρέχεται από την διπλωματική εργασία είναι η ανάγκη επανεξέτασης της state-of-the-art προσεγγίσης της βάσης δεδομένων Gene Ontology για την οργάνωση της βιολογικής γνώσης. / The study of biological systems at different levels of organization is a rapidly emerging area of computational biology. The majority of research in this field has focused on partitioning genes into biological pathways or processes. The next hurdle in moving towards the goal of understanding the cell at a systems level is to determine how these partitioned cellular processes work together to achieve the cell’s objectives. The main goal of the thesis is the prediction of various kinds of interactions that take place in the different levels of the cell and the examination of the way that these interactions cooperate in order to fullfill the cell functions. At the lower level of the cell the physical interactions exist which entail the full range of chemical bonds between proteins DNA molecules. In addition to these physical descriptions, also functional descriptions of the cellular system can be determined. These can be broadly categorized into 1) serial function interactions, such as the regulatory network interactions, 2) parallel function interactions, such as epistatic interactions (e.g. synthetic lethality) and 3) collaborative function interactions, such as protein complexes. The biological processes which exist at the highest level of the cell are groups of proteins and genes that function collaboratively. The interactions between biological processes are the highest cellular level interactions that we can detect. The detection of the aforementioned different kinds of cellular interactions as well as their conceptual linkage is the subject that the current thesis focus on. The necessary information that leads to the prediction of interactions at the higher level of the cell is the lower level physical protein interactions. Many computational methods have been implemented so far to the problem of predicting protein interactions, without achieving at the same time high performance and interpretability. At the framework of the current thesis the problem of PPI prediction is analyzed. The most contemporary experimental and computational methods for detecting PPIs are described. We will analyze their differences, advantages, disadvantages and restrictions and moreover ways for their future improvement and development are discussed. Next, we focus on the way that the topology of the physical interaction network effects on the functional interactions that take place inside the cell, such as the regulatory and the genetic interactions. A physical protein interaction network is been constructed. The topology of that network is been exploited by using kernel diffusion techniques. By varying the diffusion degree, the diffusion profiles are been created. Next, the diffusion profiles are used to characterize the topologies that connect the proteins on the physical interaction network. Moreover, the diffusion profiles are proved to be excellent tools in the improvement of the performance of the algorithms that focus on the prediction of functional interactions. Next, protein interactions are been utilized again to predict interactions at a level above the functional interactions and that is the interactions of the biological processes as they are described in the Gene Ontology database. The classical approach for studying the complex biological networks is based on the identification of interactions between the internal components metabolic or signaling pathways. Moreover, very little is known nowadays about the interactions between higher order biological systems, such as the biological processes and pathways. In the framework of the current thesis, a new methodology for the detection of interactions between biological processes is been proposed. The methodology analyzes weighted or not protein interactions. The major result of the thesis is the network constructed by using the predicted interactions between biological processes, the so called biological processes interaction network. Various databases have been developed containing information about experimentally and computationally detected human PPIs as well as their corresponding annotation data. However, these databases contain many false positive interactions, are partial and only a few of them incorporate data from various sources. To overcome these limitations, we have developed HINT-KB (http://150.140.142.24:84), a knowledge base that integrates data from various sources, provides a user-friendly interface for their retrieval, calculates a set of features of interest and computes a confidence score for every candidate protein interaction. This confidence score is essential for filtering the false positive interactions which are present in existing databases, predicting new protein interactions and measuring the frequency of each true protein interaction. For this reason, a novel machine learning hybrid methodology, called (Evolutionary Kalman Mathematical Modelling - EvoKalMaModel), was used to achieve an accurate and interpretable scoring methodology. The experimental results indicated that the proposed scoring scheme outperforms existing computational methods for the prediction of PPIs. The results of the current thesis are expected to contribute in the prediction of new potential interaction of the lower and the higher cell level for the two organisms of Human and S. Cerevisiae. Moreover, they can used for understanding the higher organizational cell levels as a compact system. Finally, the results are expected to enhance the possibility of reconstructing the state-of-the-art approaches for organizing the biological knowledge.

Στο πλαίσιο της παρούσας διδακτορικής διατριβής μελετώνται υπολογιστικά ζητήματα που προκύπτουν από τη θεωρία της κοινωνικής επιλογής. Ένα από τα κύρια θέματα της θεωρίας αυτής είναι οι εκλογές. Τα προβλήματα που σχετίζονται με τις εκλογές ανήκουν στη θεωρία ψηφοφοριών όπου βασικό πρόβλημα είναι η εύρεση του νικητή των εκλογών όταν έχουμε ως δεδομένες τις προτιμήσεις των ψηφοφόρων. Στη βιβλιογραφία υπάρχουν αρκετοί κανόνες ψηφοφορίας βάσει των οποίων γίνεται ο υπολογισμός της κατάταξης μιας ψηφοφορίας και της ανάδειξης του νικητή. Η θεωρία των ψηφοφοριών αποτελεί ένα σημαντικό κλάδο της θεωρίας της κοινωνικής επιλογής με άμεσες εφαρμογές στην κοινωνία, καθώς οι κανόνες αυτοί εφαρμόζονται στην πράξη σε βουλευτικές, δημοτικές ή τοπικές εκλογές, καθώς επίσης και σε αρκετές επιτροπές σχετικές με την λήψη συλλογικών αποφάσεων. Στη συγκεκριμένη διατριβή μελετούμε πρώτα τους κανόνες ψηφοφορίας που πρότειναν ο Dodgson και ο Young, οι οποίοι είναι σχεδιασμένοι έτσι ώστε να εντοπίζουν τον υποψήφιο που είναι διαισθητικά πιο κοντά στο να είναι ο νικητής σύμφωνα με το κριτήριο του Condorcet. Σύμφωνα με το κριτήριο αυτό, νικητής θα πρέπει να είναι ο υποψήφιος που έχει την προτίμηση της πλειοψηφίας έναντι των άλλων υποψήφιων. Ωστόσο κάτι τέτοιο δεν μπορεί να υπολογιστεί πάντα, καθώς οι προτιμήσεις της πλειοψηφίας μπορεί να είναι κυκλικές. Για παράδειγμα σε μια εκλογή με 3 υποψηφίους, ο υποψήφιος a να προτιμάται σε σχέση με τον b, ο b να προτιμάται σε σχέση με τον c, αλλά ο c να προτιμάται σε σχέση με τον a. Στην περίπτωση αυτή δεν μπορεί να καθοριστεί ο νικητής των εκλογών σύμφωνα με το κριτήριο του Condorcet. Για το λόγο αυτό χρησιμοποιούμε τους κανόνες ψηφοφορίας που προτάθηκαν από τους Dodgson και Young, οι οποίοι παρέχουν μια διαφορετική έννοια εγγύτητας ενός υποψήφιου στο να αναδειχθεί νικητής κατά Condorcet. Οι συγκεκριμένοι κανόνες αποτελούν ένα σημαντικό κομμάτι της βιβλιογραφίας της θεωρίας της Κοινωνικής Επιλογής διότι διαισθητικά παρουσιάζουν υψηλή εγγύτητα με τον κανόνα του Condorcet. Πιο συγκεκριμένα και σύμφωνα με τον κανόνα του Dodgson ισχύουν τα εξής: δεδομένου ενός συνόλου προτιμήσεων των ψηφοφόρων, ο βαθμός ενός υποψηφίου ορίζεται ως ο ελάχιστος αριθμός των ανταλλαγών που πρέπει να γίνουν μεταξύ γειτονικών υποψηφίων στην κατάταξη των ψηφοφόρων έτσι ώστε ο συγκεκριμένος υποψήφιος να αναδειχθεί νικητής κατά Condorcet. Ο υποψήφιος που έχει τον ελάχιστο βαθμό Dodgson είναι νικητής κατά Dodgson. Αντίστοιχα, σύμφωνα με τον κανόνα του Young ο βαθμός ενός υποψηφίου είναι το μέγεθος του μεγαλύτερου υποσυνόλου ψηφοφόρων έτσι ώστε, αν ληφθούν υπόψη μόνο αυτά τα ψηφοδέλτια, ο συγκεκριμένος υποψήφιος να γίνεται νικητής κατά Condorcet. Ο υποψήφιος με το μέγιστο βαθμό Young είναι νικητής κατά Young. Δυστυχώς, ο υπολογισμός του βαθμού ενός δεδομένου υποψηφίου είναι δύσκολος είτε με τον κανόνα του Dodgson είτε με τον κανόνα του Young. Για αυτό το λόγο τα υπολογιστικά ζητήματα που προκύπτουν και μελετώνται στην παρούσα διατριβή αφορούν στην προσέγγιση των δυο αυτών κανόνων ψηφοφορίας. Πιο συγκεκριμένα παρουσιάζονται δύο αλγόριθμοι που προσεγγίζουν το βαθμό ενός υποψηφίου σύμφωνα με τον κανόνα του Dodgson: ένας άπληστος αλγόριθμος και ένας αλγόριθμος βασισμένος σε γραμμικό πρόγραμμα. Οι δυο αυτοί αλγόριθμοι έχουν λόγο προσέγγισης H_{m-1}, όπου m είναι ο αριθμός των υποψηφίων και H_{m-1} είναι ο (m-1)-ος αρμονικός αριθμός. Επίσης, αποδεικνύεται ότι δεν υπάρχει αλγόριθμος πολυωνυμικού χρόνου που να προσεγγίζει το βαθμό Dodgson κατά λογαριθμικό παράγοντα, εκτός εάν υπάρχουν για τα προβλήματα της κλάσης NP αλγόριθμοι ψευδο-πολυωνυμικού χρόνου. Παρότι διαισθητικά υπερέχει ο άπληστος αλγόριθμος, στη συγκεκριμένη διατριβή υποστηρίζουμε ότι ο αλγόριθμος που είναι βασισμένος σε γραμμικό πρόγραμμα έχει πλεονέκτημα από την οπτική της θεωρίας της κοινωνικής επιλογής. Επιπλέον, αποδεικνύεται ότι ο υπολογισμός κάθε λογικής προσέγγισης της κατάταξης που παράγεται από τον κανόνα Dodgson είναι ένα υπολογιστικά δύσκολο πρόβλημα, γεγονός που εξηγεί, από την πλευρά της θεωρίας της πολυπλοκότητας, το ότι έχουν παρατηρηθεί μεγάλες διαφορές κατά τη σύγκριση εκλογών Dodgson με απλούστερους κανόνες ψηφοφορίας που εμπεριέχονται στη βιβλιογραφία της θεωρίας της κοινωνικής επιλογής. Τέλος, αποδεικνύεται ότι το πρόβλημα υπολογισμού του βαθμού ενός υποψηφίου σύμφωνα με τον κανόνα του Young είναι επίσης υπολογιστικά δύσκολο. Αυτό οδηγεί σε ένα αποτέλεσμα μη προσεγγισιμότητας για την κατάταξη υποψηφίων σε μια εκλογή σύμφωνα με τον κανόνα του Young. Αν και ο κανόνας του Dodgson είναι ένας από τους πιο καλά μελετημένους κανόνες ψηφοφορίας, παρουσιάζει σοβαρές ελλείψεις, τόσο από υπολογιστικής άποψης --- είναι υπολογιστικά δύσκολο ακόμη και να προσεγγιστεί ο βαθμός Dodgson ενός υποψηφίου --- όσο και από την πλευρά της κοινωνικής επιλογής, καθώς αποτυγχάνει σε βασικές επιθυμητές ιδιότητές της, όπως είναι η μονοτονία και η ομοιογένεια. Ωστόσο, αυτό δεν αποκλείει την ύπαρξη προσεγγιστικών αλγορίθμων για τον κανόνα του Dodgson που είναι μονότονοι ή ομοιογενείς, οπότε τίθεται το ερώτημα ύπαρξης τέτοιων αλγόριθμων. Στη διατριβή αυτή δίνονται οριστικές απαντήσεις στα ερωτήματα αυτά. Παρουσιάζεται ένας μονότονος αλγόριθμος εκθετικού χρόνου που πετυχαίνει λόγο προσέγγισης του βαθμού Dodgson ίσο με 2 και το αποτέλεσμα συμπληρώνεται με ένα αυστηρό αντίστοιχο κάτω φράγμα. Παρουσιάζεται επίσης ένας μονότονος προσεγγιστικός αλγόριθμος πολυωνυμικού χρόνου με λόγο O(logm) (όπου m είναι ο αριθμός των υποψηφίων): και στην περίπτωση αυτή το αποτέλεσμα είναι βέλτιστο, λόγω ύπαρξης αντίστοιχου κάτω φράγματος. Επιπλέον, αποδεικνύεται ότι μια μικρή παραλλαγή σε ένα γνωστό κανόνα ψηφοφορίας δίνει ένα μονότονο, ομοιογενή, O(m logm)-προσεγγιστικό αλγόριθμο πολυωνυμικού χρόνου, με τον καλύτερο δυνατό λόγο προσέγγισης, ακόμη και αν αυτό που μας ενδιαφέρει είναι μόνο η ομοιογένεια. Τέλος, μελετώνται διάφορες πρόσθετες ιδιότητες κοινωνικής επιλογής, για τις οποίες δεν υπάρχει αλγόριθμος με λόγο προσέγγισης που να εξαρτάται μόνο από το m . Αυτά τα αποτελέσματα της προσεγγισιμότητας του κανόνα αυτού αποτελούν σημαντική προσφορά της διατριβής καθώς μπορούν να θεωρηθούν ως κανόνες που υπολογίζονται σε πολυωνυμικό χρόνο και πληρούν μάλιστα επιθυμητές κοινωνικές ιδιότητες, ενώ ταυτόχρονα διέπονται και από την φιλοσοφία του κανόνα που θέσπισε ο Dodgson. Ένα άλλο σημαντικό υπολογιστικό πρόβλημα με το οποίο ασχολείται η παρούσα διατριβή είναι αυτό της δωροδοκίας των εκλογών. Στο πρόβλημα της δωροδοκίας μπορεί κάποιος με δεδομένο ένα χρηματικό προϋπολογισμό να αλλάξει τις προτιμήσεις των ψηφοφόρων ώστε να αναδειχθεί νικητής των εκλογών ο υποψήφιος της αρεσκείας του. Στη συγκεκριμένη διατριβή μελετώνται κανόνες ψηφοφορίας που βασίζονται στη βαθμολόγηση των υποψηφίων. Πιο συγκεκριμένα μελετάται η τάξη των κανόνων ψηφοφορίας όπου κάθε ψηφοφόρος εκχωρεί κ βαθμούς στον υποψήφιο που προτιμά ως πρώτο, λ βαθμούς στον υποψήφιο που προτιμά ως δεύτερο και 0 βαθμούς σε όλους τους υπόλοιπους υποψηφίους. Αποδεικνύεται ότι για αυτήν την τάξη των κανόνων βαθμολόγησης η δωροδοκία είναι ένα υπολογιστικά δύσκολο πρόβλημα. Στους κανόνες που βασίζονται στην βαθμολόγηση των υποψηφίων περιλαμβάνονται αυτοί της πλειοψηφίας και της 2-έγκρισης όπου μια βέλτιστη στρατηγική δωροδοκίας μπορεί εύκολα να υπολογιστεί, καθώς επίσης και ο κανόνας της 3-έγκρισης όπου η δωροδοκία είναι ένα υπολογιστικά δύσκολο πρόβλημα. Λαμβάνοντας υπόψιν την πολυπλοκότητα αυτών των κανόνων εξάγεται το συμπέρασμα ότι οι κανόνες που μελετήθηκαν είναι εκ των πιο απλών που δεν είναι ευάλωτοι στη δωροδοκία. / In this PhD thesis we study computational problems arising from the theory of social choice. One main aspect of Computational Social Choice is voting theory. The most important problem of voting theory is the computation of the winner of the elections when we have as input the preferences of the voters. In the literature there are many voting rules according to which the computation of the winner of the elections is done. Voting theory is a seminal subject in the Computational Social Choice theory with applications in the society. Voting rules are widely used in government and municipal or local elections and also in committees for taking decisions. In this thesis we start by considering voting rules proposed by Dodgson and Young. These rules are both designed to find an alternative closest to being a Condorcet winner. According to the Condorcet criterion, the winner of the elections should be the one that the majority of the voters prefer in relation to every other candidate. Unfortunately, the preferences of the majority may be circular. For example, in an election with 3 candidates, candidate a is preferred to b by the majority and b is preferred in relation to c, but c is preferred to a. Then a Condorcet winner does not exist. Each of these voting rules provide a different notion of proximity of how close they are to Condorcet rule. In the Dodgson rule the score of a candidate, given a set of preferences, is the minimum number of exchanges between adjacent candidates in order for the specific candidate to become a Condorcet winner. The Dodgson winner is the candidate with the minimum Dodgson score. In the Young rule the score of a candidate is the size of the largest subset of voters, when taking in account only these votes, the specific candidate becomes a Condorcet winner. The Young winner is the candidate with the maximum Young score. The score of a given alternative is known to be hard to compute under either rule and so the computational problems that arise and we consider are related to the approximation of the voting rules proposed by Dodgson and Young. We put forward two algorithms for approximating the Dodgson score: a combinatorial, greedy algorithm and an LP-based algorithm, both of which yield an approximation ratio of H_{m-1}, where m is the number of alternatives and H_{m-1} is the (m-1)st harmonic number. We also prove that there is no polynomial time algorithm that approximates the Dodgson score by (1/2-ε)lnm, unless problems in NP have quasi-polynomial time algorithms. Despite the intuitive appeal of the greedy algorithm, we argue that the LP-based algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgson's rule is NP-hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the social choice theory literature when comparing Dodgson elections with simpler voting rules. Also, we show that the problem of calculating the Young score is NP-hard to approximate by any factor. This leads to an inapproximability result for the Young ranking. Although Dodgson's rule is one of the most well-studied voting rules, it suffers from serious deficiencies, both from the computational point of view --- it is NP-hard even to approximate the Dodgson score within sublogarithmic factors --- and from the social choice point of view --- it fails basic social choice desiderata such as monotonicity and homogeneity. However, this does not preclude the existence of approximation algorithms for Dodgson that are monotonic or homogeneous, and indeed it is natural to ask whether such algorithms exist. In this thesis we give definitive answers to these questions. We design a monotonic exponential-time algorithm that yields a 2-approximation to the Dodgson score, while matching this result with a tight lower bound. We also present a monotonic polynomial-time O(logm)-approximation algorithm (where m is the number of alternatives); this result is tight as well due to a complexity-theoretic lower bound. Furthermore, we show that a slight variation on a known voting rule yields a monotonic, homogeneous, polynomial-time O(m logm)-approximation algorithm, and establish that it is impossible to achieve a better approximation ratio even if one just asks for homogeneity. We complete the picture by studying several additional social choice properties; for these properties, we prove that algorithms with an approximation ratio that depends only on m do not exist. In this thesis we consider also the important computational problem of bribery in elections, where the winning candidate is computed using a scoring voting rule. In the bribery problem we have an external agent who wants to change the preferences of some voters to make his favorite candidate win the election given a budget. In this thesis we consider scoring voting rules where the voter gives to the first candidate κ points, λ points to his second most preferred candidate and zero points to all other candidates. We prove that for this class of rules bribery is a computationally hard problem. The class of scoring voting rules includes plurality and 2-approval for which an optimal bribing strategy can be computed efficiently as well as 3-approval which is hard to bribe. Concluding we derive that the class of rules we consider is one of the most simple scoring voting rules that are resistant to bribery.

Ο πρωταρχικός στόχος αυτής της εργασίας είναι η υλοποίηση μιας βιομηχανικής διάταξης σε εργαστηριακή κλίμακα στην οποία να συνεργάζονται ένα στερεοσκοπικό σύστημα και ένας ρομποτικός βραχίονας. Πιο συγκεκριμένα, η διαδικασία χωρίζεται σε δύο μέρη, την αναγνώριση στο χώρο των επιθυμητών αντικειμένων και την οδήγηση βάση αυτής του ρομποτικού βραχίονα. Για το πρώτο μέρος έγινε χρήση της βιβλιοθήκης OpenCV σε γλώσσα C++ και ως στερεοσκοπικό υλικό χρησιμοποιήθηκαν δύο παράλληλα διατεταγμένες κάμερες τύπου webcam. Η διαδικασία που ακολουθήθηκε για την αναγνώριση θέσης χωρίστηκε σε αρκετά βήματα. Αρχικά δημιουργήθηκε ένα πρόγραμμα το οποίο αποθηκεύει καρέ από τις δύο κάμερες στα οποία απεικονίζεται ένα μοτίβο βαθμονόμησης. Στη συνέχεια, αυτές οι εικόνες εισάγονται στον κώδικα βαθμονόμησης με στόχο να υπολογιστούν οι εγγενείς και εξωγενείς παράμετροι των καμερών. Έπειτα, με τη χρήση των παραμέτρων αυτών και τη θεωρία της επιπολικής γεωμετρίας μπορεί να γίνει η αναγνώριση θέσης ενός αντικειμένου στο χώρο. Τέλος, χρησιμοποιείται ένας αλγόριθμος εντοπισμού του κέντρου ενός αντικειμένου στην οθόνη με βάση το χρώμα έτσι ώστε να καθοριστεί για ποιο αντικείμενο ο αλγόριθμος θα υπολογίσει τη θέση. Στο δεύτερο μέρος χρησιμοποιήθηκε ο ρομποτικός βραχίονας Katana s400 6M90G της εταιρείας Neuronics, ο οποίος προγραμματίστηκε σε γλώσσα C++, σε περιβάλλον Visual Studio 2008. Αρχικά, βρέθηκαν οι γωνίες Euler της αρπάγης, για διαφορετικές προσεγγίσεις του προσανατολισμού της. Με τον συνδυασμό των συντεταγμένων του αντικειμένου, που βρίσκονται από το στερεοσκοπικό σύστημα καθοδηγείται το Katana ώστε να το πιάσει. Τα πειράματα που διεξαχθήκαν περιλάμβαναν την αρπαγή στάσιμων αντικειμένων με γενικό και οριζόντιο προσανατολισμό εργαλείου. Τέλος, πραγματοποιήθηκαν πειράματα με αντικείμενα εν κινήσει, τυχαίας θέσης με γενικό, κάθετο και οριζόντιο προσανατολισμό αρπάγης. / The primary objective of this thesis is the implementation of an industrial system at laboratory scale in which a stereo system collaborates with a robotic arm. More specifically, the process is divided into two parts, the recognition of the desired objects and the manipulation of the robotic arm. In the first part were used the OpenCV library, in C ++ language and two parallel web-cameras. The procedure for the recognition of the objects, was divided into several steps. Initially a number of images were inserted in the calibration algorithm in order to estimate the intrinsic and extrinsic camera parameters. Then, using these parameters and the epipolar geometry it was possible to recognize the position of an object in 3D space. Finally, an algorithm is used to locate the center of an object on the screen by color in order to determine for what object the algorithm will calculate the position. In the second part was used the robotic arm Katana s400 6M90G by Neuronics, programmed in C ++, in Visual Studio 2008. Initially, the Euler angles of the gripper for different orientations were found. Given the coordinates of the objects, provided by the stereo system, the Katana arm was guided to grasp them. The experiments that were conducted included the grasping of stationary objects in a general and horizontal orientation of the Katana tool. Finally, experiments were performed with objects in motion and random position in general, vertical and horizontal orientation of the gripper.

Στόχος της παρούσας διπλωματικής εργασίας είναι η μελέτη και η ανάπτυξη ενός ρομποτικού οχήματος το οποίο θα είναι ικανό να πλοηγηθεί αυτόνομα στο χώρο αναγνωρίζοντας και αποφεύγοντας τα πιθανά εμπόδια στο περιβάλλον που θα κινηθεί. / The aim of this thesis is to study and develop a robotic vehicle that will be able to navigate autonomously in space by identifying and avoiding potential barriers in the environment that it will move.

Το πρόβλημα της αντιστοίχισης εικόνων είναι ένα από τα σημαντικότερα στο πεδίο της υπολογιστικής όρασης, αφού η ευθυγράμμιση δύο ή περισσότερων εικόνων χρησιμοποιείται τουλάχιστον σαν στάδιο προεπεξεργασίας σε ένα μεγάλο αριθμό εφαρμογών. Στην εργασία αυτή μας απασχόλησε το πρόβλημα της στοίχισης εικόνων στις οποίες οι φωτομετρικές παραμορφώσεις είναι τοπικές και δεν μπορούν να μοντελοποιηθούν με το γενικό σφαιρικό μοντέλο της αντίθεσης και της φωτεινότητας, ή/και τμήματα των προς στοίχιση εικόνων είναι αποκλεισμένα από τη μια από αυτές. Για την αντιμετώπιση των παραπάνω προβλημάτων, η αντιστοίχηση των εικόνων προσεγγίστηκε μέσω της σταθμισμένης ελαχιστοποίησης μετρικών σφάλματος που βασίζονται στο τετραγωνικό σφάλμα. Συγκεκριμένα, εκμεταλλευόμαστε την αμεταβλητότητα της κανονικοποιημένης κλίσης μιας εικόνας σε τοπικές φωτομετρικές παραμορφώσεις και τη δυνατότητα στοίχισης κάθε ζεύγους αντίστοιχων εικονοστοιχείων των υπό στοίχιση εικόνων με την μεγιστοποίηση της μεταξύ τους συσχέτισης. Έτσι πετυχαίνουμε την αποσύνδεση του αρχικού προβλήματος σε δύο υποπροβλήματα η λύση των οποίων καταλήγει σε δύο υπερκαθορισμένα συστήματα γραμμικών εξισώσεων, καθένα εκ των οποίων έχει ως αγνώστους τις ανά κατεύθυνση παράμετρες του μετασχηματισμού που αναζητούμε για την εξάλειψη της γεωμετρικής παραμόρφωσης και ως δεξιό μέλος τις τιμές των φωτομετρικών παραμορφώσεων. Τελικά, με την επιλογή δύο κατάλληλων υποσυνόλων των προαναφερθέντων γραμμικών εξισώσεων, που εξασφαλίζουν την εφικτότητα των επιμέρους λύσεων οδηγούμαστε στον προσδιορισμό των βέλτιστων παραμέτρων. Η προτεινόμενη τεχνική δοκιμάστηκε στη βάση προσώπων Yale Β που έχει χρησιμοποιηθεί από άλλες τεχνικές αντιστοίχισης που είναι ειδικά προσαρμοσμένες για την αντιστοίχιση προσώπων. Η απόδοση της προτεινόμενης τεχνικής είναι πολύ καλή και υπερτερεί και στα ποσοστά σύγκλισης αλλά και στην ακρίβεια των λύσεων από την απόδοση των άλλων τεχνικών τόσο στη στοίχιση εικόνων που έχουν υποστεί γεωμετρικές παραμορφώσεις (από πολύ μικρές μέχρι και πολύ έντονες) όσο και σε εικόνες με διαφορετικές έντονες φωτομετρικές παραμορφώσεις. Επίσης, η προτεινόμενη τεχνική δοκιμάστηκε στις βάσεις του Affine Covariance Regions του University of Oxford στις οποίες το περιεχόμενο των εικόνων είναι γενικό και οι ειδικού σκοπού τεχνικές αποτυγχάνουν, με εξίσου πολύ καλή απόδοση. / The image registration problem is one of the most important problems in the field of computer vision, since the process of aligning two or more images is used, at least as a preprocessing step, in many applications. In this work, we employed the problem of image alignment in which the photometric deformations are local and can not be modeled with the general spherical model of contrast and brightness, and / or portions of images to align are occluded. To address these problems, the image registration was approached by minimizing the weighted error metric based on squared error. In particular, we exploit the invariance of the normalized image gradient in local photometric deformations so we can align each pair of corresponding pixels in the images by maximizing the correlation between them. Thus, we achieve to dissolve the original problem into two subproblems the solution of which leads to two over-determined systems of linear equations, each of which has the direction parameters of the transformation we seek to estimate as unknowns and as right member the values of photometric deformations. Ultimately, the choice of two suitable subsets of the above linear equations, ensuring the feasibility of individual solutions we are lead to the identification of best parameters. The proposed technique was tested in Yale B face database which has been used by other mapping techniques adapted to matching persons. The performance of the proposed technique is very good and superior at the convergence rates and the accuracy of the solutions to the performance of other techniques concerning both images that have undergone geometrical deformation (from very small to very intense) and images in different intense photometric deformations. Also, the proposed technique was tested on database of Affine Covariance Regions of the University of Oxford in which the content of the images is general and special-purpose techniques fail, with equally good performance.

Στην διατριβή αυτή εξετάζεται η αποδοτικότητα αλγορίθμων υπολογιστικής νοημοσύνης σε προβλήματα αριθμητικής βελτιστοποίησης, αναπτύσσονται τροποποιήσεις και βελτιώσεις των μεθόδων και εισάγεται ένα νέο σχήμα της μεθόδου Βελτιστοποίησης με Σμήνος Σωματιδίων, το οποίο ενοποιεί διαφορετικές εκδόσεις της συνδυάζοντας τα χαρακτηριστικά τους, μαζί με την θεωρητική ανάλυσή του. / The main goal of this thesis was the investigation of the performance of computational intelligence algorithms on numerical optimization problems, the development of modifications and improvements of the algorithms, as well as the development of a new scheme of the Particle Swarm Optimization algorithm that harnesses its main variants, along with its theoretical analysis.

- / -

- / -

Η ανακάλυψη των microRNA γονιδίων το 1993 έφερε επανάσταση στα όσα γνωρίζαμε από το κεντρικό δόγμα της Βιολογίας για τη σύνθεση των πρωτεϊνών και τη ρύθμιση της πρωτεϊνικής έκφρασης. Αυτό γιατί τα microRNA γονίδια δεν κωδικοποιούν κάποια πρωτεΐνη αλλά αντί αυτού παράγουν μικρά μόρια μεγέθους περίπου 22 νουκλεοτιδιών. Τα μόρια αυτά αλληλεπιδρούν με το mRNA και συγκεκριμένα βρίσκουν στόχους στις 3 UTR περιοχές άλλων γονιδίων και αλληλεπιδρούν με βάση την αρχή της συμπληρωματικότητας Watson-Crick. Αποτέλεσμα αυτής της πρόσδεσης είναι η καταστολή της πρωτεϊνικής έκφρασης του γονιδίου στόχου μέσω αναστολής της μετάφρασης ή μέσω της υποβάθμισης του mRNA. Μετά την ανακάλυψη των microRNA και του τρόπου αλληλεπίδρασης τους ήταν φυσικό να ακολουθήσουν εκτεταμένες έρευνες για τις κυτταρικές διεργασίες τις οποίες ρυθμίζουν αλλά και σε ποιών γονίδιων τη ρύθμιση λαμβάνουν μέρος. Ως αποτέλεσμα προέκυψε ότι σε πολλές γνωστές ασθένειες παρουσιάζεται άμεση συσχέτιση με ρύθμιση από microRNA. Τέτοια περίπτωση αποτελεί και η ασθένεια του καρκίνου η οποία σε συνδυασμό με την «λεπτή» ρύθμιση που προκαλούν τα microRNA δίνει ελπίδες για νέες μοριακές θεραπείες. Αυτά είναι μερικά παραδείγματα από τα οποία μπορούμε να καταλάβουμε τη μεγάλη σημασία των microRNA και την ανάγκη για αποδοτική πρόβλεψη τους. Εξαιτίας του μικρού τους μεγέθους αλλά και του μικρού τους ποσοστού σε σχέση με το μέγεθος του γονιδιώματος (περίπου 3%) ο πειραματικός τους εντοπισμός χαρακτηρίζεται εξαιρετικά δύσκολος. Για το λόγο αυτό έχουν επιστρατευτεί αρκετές μέθοδοι Υπολογιστικής Νοημοσύνης και Αλγόριθμοι οι οποίοι μπορούν να «ξεχωρίσουν» τα πραγματικά γονίδια από τα ψεύτικα γονίδια δημιουργώντας έτσι μοντέλα πρόβλεψης. Μέχρι στιγμής έχουν χρησιμοποιηθεί σαν μέθοδοι ταξινόμησης, Support Vector Machine, δίκτυα Bayes και άλλες πιθανοτικές μέθοδοι όπως τα Hidden Markov μοντέλα .Όλες οι μέθοδοι αυτού του είδους βασίζονται στον υπολογισμό αρκετών χαρακτηριστικών για τα microRNA που σχετίζονται με το ακολουθιακό περιεχόμενο, με τη δομή τους στο χώρο αλλά και με θερμοδυναμικά στοιχεία των μορίων. Σε μεγάλο βαθμό η αποδοτικότητα πρόβλεψης βασίζεται στην επιλογή των πιο αντιπροσωπευτικών χαρακτηριστικών και στη βελτιστοποίηση των παραμέτρων της υπολογιστικής μεθόδου που χρησιμοποιείται χωρίς μέχρι τώρα να έχει βρεθεί μια αξιόπιστη λύση. Στην παρούσα διπλωματική εργασία αρχικά προτείναμε μια νέα υβριδική μεθοδολογία για ταυτόχρονη ταξινόμηση microRNA γονιδίων, εξαγωγή χαρακτηριστικών και υπολογισμό παραμέτρων. Η προτεινόμενη μεθοδολογία χρησιμοποιεί τις καινοτόμες τεχνικές του Εξελικτικού Προγραμματισμού και συγκεκριμένα τους Γενετικούς Αλγορίθμους για την εξαγωγή χαρακτηριστικών και βελτιστοποίηση παραμέτρων καθώς και Support Vector Machine για ταξινόμηση. Απώτερος στόχος της παρούσας εργασίας ήταν να αναπτυχθεί μια ολοκληρωμένη διαδικτυακή πλατφόρμα η οποία επιτρέπει αρχικά υπολογισμό χαρακτηριστικών για τις γονιδιακές ακολουθίες που θα εισάγει ο χρήστης και κατά δεύτερον δίνει την πρόβλεψη του ταξινομητή για το αν είναι ή όχι microRNA γονίδια μέσω ενός φιλικού περιβάλλοντος. Επιπλέον, ενσωματώθηκαν τα περισσότερα microRNA χαρακτηριστικά που έχουν προταθεί στη βιβλιογραφία και η αποδοτικότητα πρόβλεψης του ταξινομητή βελτιώθηκε μέσω της προτεινόμενης υβριδικής μεθόδου. Ενσωματώσαμε διάφορα πακέτα για τον υπολογισμό των χαρακτηριστικών όπως το Vienna RNA Package και το UnaFold και αυτό το κομμάτι της εργασίας σχετίζεται με την έρευνα για τη θερμοδυναμική και φυσικοχημική συμπεριφορά των μικρών RNA μορίων. Καινοτόμο στοιχείο αποτελεί το γεγονός ότι ο υπολογισμός των χαρακτηριστικών γίνεται με τέτοιο τρόπο ώστε να ευνοείται στη συνέχεια η εφαρμογή μεθόδων Υπολογιστικής Νοημοσύνης. Επιπλέον στο σύστημα ενσωματώσαμε βάση δεδομένων η οποία αποθηκεύει τις επεξεργασμένες ακολουθίες και τα υπολογισμένα χαρακτηριστικά δίνοντας ώθηση για την κατασκευή νέων συνόλων δεδομένων. Τέλος αυτή η δυνατότητα ανάκτησης πληροφορίας κάνει το σύστημα μας μια ολοκληρωμένη πλατφόρμα μελέτης μικρών RNA μορίων και πρόβλεψης microRNA γονιδίων. / The discovery of microRNA genes in 1993 challenged the view of the Central Dogma of Biology and introduced a new layer of complexity in which RNA is not only a carrier of gene information but also a mediator of gene expression and protein synthesis. Typically, microRNA genes are short non-coding (~20-22 nt) RNAs that do not encode proteins, but instead they produce small RNA molecules. These molecules can regulate mRNA target genes by binding to the 3’ UTR of mRNA in accordance to Watson-Crick complementarity for cleavage or translational repression. MicroRNAs have been a major object of study as they have been found to be involved in some basic biological processes. These observations underline the importance of normal microRNA homeostasis on functions such as development, differentiation, apoptosis and proliferation. Dysregulation of miRNA is fundamental to the pathogenesis of many diseases and it has been long suspected that miRNA expression can be deregulated in cancer and abnormal miRNA activity may lead to tumorgenesis. From all the above, it is obvious that the better understanding of miRNA mechanism and function may lead to new and more sophisticated design of clinical therapies. Consequently, the identification of novel microRNA genes is a challenging bioinformatics problem. The experimental identification has some important drawbacks: the small size of microRNA genes in comparison to the size of the genome, cost and time, and low sensitivity. To overcome these technical problems a lot of computational methods have been proposed and several Artificial Intelligence techniques have been applied to distinguish real pre-miRNAs from pseudo hairpins. Support Vector Machines, Naïve Bayes and other probabilistic algorithms such as Hidden Markov Models have been successfully developed as classification methods. All these computational methods rely on the computation of several sequential, structural and thermodynamical microRNA features. In addition, the prediction efficiency is related to the extraction of the most discriminative features and to the optimization of the parameters. At first, this thesis presents a hybrid approach for simultaneous microRNA classification, feature extraction and parameters optimization. We took advantage of the innovative techniques of Evolutionary Programming and we introduced an embedded classification method, which combines the efficiency and robustness of Support Vector Machines with Genetic Algorithms for feature selection and parameters optimization. Secondly, objective of this thesis was the development of an online platform for effective microRNA genes prediction. The prediction model is based on our classification model and we used a significant feature subset that the proposed methodology revealed to be consistent. Also, we provided the opportunity to calculate all the microRNA features that have been proposed in the literature. We incorporated different packages such as the Vienna RNA package and UnaFold package and we introduced some new features with high discriminative power. This work is related to biophysics and thermodynamics of small RNA molecules and it can be applied to other categories of regulatory molecules. Also, the provided service in accordance to the feature calculation will encourage the application of other Artificial Intelligence Techniques in identifying microRNAs. We hope that the construction of new datasets will contribute to the Development of new Machine Learning methodologies. Furthermore, our tool maintains a Database about predicted microRNA sequences plus some informating metadata about them. Finally it can act as an integraded system and the usage of metadata enables information retrieval.