Παράλληλοι αλγόριθμοι εξόρυξης και ανάλυσης δεδομένων σε πλέγματα υπολογιστών με εφαρμογές στη βιοπληροφορική

Abstract

Although Bioinformatics and Computational Biology are often confused as the same multidisciplinary field, there exist several differences that distinguish them. Bioinformatics focuses on analysis and processing of biological data and consequently the promotion of research in algorithms and technical level of both the methods and theory to solve formal problems of data management. On the other hand, Computational Biology aims to solve specific problems in Biology, utilizing the potential of computers for testing and evaluating hypothesis. Nevertheless the two fields share several areas of convergence. Proteomics is one of these areas and is also the focus of extensive ongoing research. Proteomics is essentially the large-scale study of proteins, ranging from the identification and analysis of their structure to the prediction of their functionality and the construction of metabolic pathways. In recent years there has been a shift in research interest in Bioinformatics from genomics to proteomics, which is widely considered as the next step in the study of biological systems. While the genome of an organization remains fairly constant in different cells of the same organization, the proteome of a species is highly differentiated from cell to cell. In previous years, genomics and proteomics could only focus on one gene or protein at a time. However, the technological advancements in Life Sciences has led to an exponentially growing amount of data. For this reason there has been a shit in research, from hypothesis-driven to data-driven studies. As the demand for automated analysis of large and distributed data grows, new challenges emerge both regarding the modeling and the development of algorithms for high throughput data analysis. This thesis presents a general methodology for Bioinformatics Algorithm Development in Grid Environments (BADGE) aiming at precisely these challenges. Grid Computing can be viewed as a virtual computing architecture that provides the ability to perform higher throughput processing by taking advantage of many computers geographically dispersed and connected by a network. Bioinformatics applications can benefit greatly from the increased availability, reliability and efficiency of computational resources, in such a distributed environment. There is already considerable research in progress toward applying parallel computing techniques on bioinformatics methods, such as multiple sequence alignment, gene expression analysis and phylogenetic studies. In order to cope with the dimensionality issue, most machine learning methods focus on specific groups of proteins or reduce either the size of the original data set or the number of attributes involved. Grid Computing can potentially provide an alternative solution to this problem, by combining multiple approaches in a seamless way. The BADGE methodology presented in this thesis, couples the strengths of the Grid with the specific needs and constraints of proven bioinformatics approaches. In order to evaluate the BADGE methodology, we applied it on several existing algorithms and on a series of new algorithms, which were developed to address issues both in Bioinformatics and in other research areas as well. The bioinformatics algorithms we designed mainly focus on proteomics and aim to provide solution to the problems of protein classification, prediction of protein function, and abnormal gene detection. Finally, the methodology was also used in the development of an algorithm in Computational Chemistry, addressing the problem of identifying molecular knots in three dimensional space. In every case, it was shown, both theoretically and experimentally, that the new approach presents clear advantages over conventional approaches in terms of time performance and robustness.

Αν και οι επιστήμες της Βιοπληροφορικής και της Υπολογιστικής Βιολογίας συχνά συγχέονται ως το ίδιο διεπιστημονικό πεδίο, παρουσιάζουν αρκετά σημεία που τις διαφοροποιούν σε σημαντικό βαθμό. Η Βιοπληροφορική αφορά κυρίως την ανάλυση και την επεξεργασία των βιολογικών δεδομένων και, κατά συνέπεια, την προώθηση της έρευνας σε αλγοριθμικό και τεχνικό επίπεδο, τόσο των μεθόδων όσο και της θεωρίας για την επίλυση τυπικών προβλημάτων διαχείρισης δεδομένων. Από την άλλη πλευρά, η επιστήμη της Υπολογιστικής Βιολογίας στοχεύει στην επίλυση συγκεκριμένων προβλημάτων Βιολογίας, αξιοποιώντας τις εντυπωσιακές δυνατότητες των υπολογιστών για τη δοκιμή και την αξιολόγηση υποθέσεων. Αυτό βέβαια δε σημαίνει ότι δεν υπάρχουν αρκετές περιοχές σύγκλισης των δύο πεδίων. Ο χώρος της πρωτεομικής, δηλαδή της μελέτης των πρωτεϊνών, είναι ένας από αυτούς τους χώρους, ο οποίος ταυτόχρονα αποτελεί και ένα από τα σημεία εκτενούς έρευνας αυτή τη στιγμή. Η πρωτεομική είναι στην ουσία η μελέτη σε μεγάλη κλίμακα των πρωτεϊνών, από τον προσδιορισμό και την ανάλυση της δομής τους έως την πρόβλεψη της λειτουργίας τους και την κατασκευή μεταβολικών μονοπατιών. Τα τελευταία χρόνια υπήρξε μια μετατόπιση του ερευνητικού ενδιαφέροντος στη Βιοπληροφορική, από την ανάλυση γενετικών δεδομένων στην πρωτεομική, η οποία θεωρείται από πολλούς ως το επόμενο βήμα στη μελέτη των βιολογικών συστημάτων. Ενώ η γενετική πληροφορία σε ένα οργανισμό είναι λίγο πολύ αμετάβλητη τόσο στο χρόνο όσο και ανάμεσα στα διαφορετικά κύτταρα του ιδίου οργανισμού, το σύνολο των πρωτεϊνών που εκφράζονται κάθε χρονική στιγμή παρουσιάζει τεράστιες διαφορές μεταξύ κυττάρων. Επίσης, στα προηγούμενα έτη, μελέτες τόσο του γονιδιώματος όσο και των πρωτεϊνών μπορούσαν να επικεντρωθούν μόνο σε μία πρωτεΐνη ή γονίδιο τη φορά. Ωστόσο, η πρόοδος της τεχνολογίας στις βιοεπιστήμες οδήγησε σε μια εκθετικά αυξανόμενη ποσότητα δεδομένων. Για αυτό το λόγο υπήρξε μια στροφή στην έρευνα, από μελέτες γύρω από υποθέσεις προς μελέτες με γνώμονα τα διαθέσιμα δεδομένα. Καθώς η ζήτηση για αυτοματοποιημένη ανάλυση μεγάλου και κατανεμημένου όγκου δεδομένων αυξάνεται διαρκώς, αναδύονται νέες προκλήσεις τόσο στη μοντελοποίηση των προσεγγίσεων όσο και στην ανάπτυξη αλγορίθμων και τεχνικών ανάλυσης δεδομένων υψηλής ρυθμαπόδοσης. Στα πλαίσια της διατριβής παρουσιάζεται μια γενικευμένη μεθοδολογία ανάπτυξης αλγορίθμων σε περιβάλλοντα Πλέγματος Υπολογιστών, η οποία στοχεύει σε ακριβώς αυτές τις προκλήσεις. Ένα Πλέγμα Υπολογιστών μπορεί να θεωρηθεί ως μια εικονική υπολογιστική αρχιτεκτονική, η οποία παρέχει τη δυνατότητα εκτέλεσης εφαρμογών με υψηλότερη απόδοση, αξιοποιώντας πολλούς υπολογιστικούς πόρους γεωγραφικά κατανεμημένους και συνδεδεμένους μέσω δικτύου. Οι εφαρμογές Βιοπληροφορικής είναι ιδιαιτέρως κατάλληλες για ένα τέτοιο περιβάλλον, από άποψη διαθεσιμότητας, αξιοπιστίας και αποτελεσματικότητας των υπολογιστικών πόρων. Υπάρχει ήδη σημαντική πρόοδος στην έρευνα όσον αφορά την εφαρμογή παράλληλων υπολογιστικών τεχνικών σε προσεγγίσεις Βιοπληροφορικής, όπως οι Πολλαπλές Συστοιχίσεις Ακολουθιών, η ανάλυση Γονιδιακών Εκφράσεων και οι Φυλογενετικές Μελέτες. Για να αντιμετωπισθεί ο όγκος δεδομένων σε αυτές τις περιπτώσεις, οι περισσότερες μέθοδοι μηχανικής μάθησης επικεντρώνονται σε συγκεκριμένες ομάδες δεδομένων, είτε μειώνοντας το μέγεθος των αρχικών δεδομένων, είτε μειώνοντας τον αριθμό των χαρακτηριστικών που συμμετέχουν στη μελέτη. Τα Πλέγματα Υπολογιστών μπορούν δυνητικά να αποτελέσουν μια εναλλακτική λύση για το πρόβλημα αυτό, συνδυάζοντας πολλαπλές προσεγγίσεις με ομοιογενή τρόπο. Η γενικευμένη μεθοδολογία που αναπτύχθηκε στα πλαίσια της διατριβής γεφυρώνει την απόσταση μεταξύ των Πλεγμάτων Υπολογιστών και των ιδιαίτερων αναγκών και προβλημάτων που εμφανίζει η πλειοψηφία των προσεγγίσεων Βιοπληροφορικής. Για να αξιολογηθεί η Γενικευμένη Μεθοδολογία εφαρμόσθηκε σε υπάρχοντες αλγορίθμους καθώς και σε μια σειρά νέων αλγορίθμων που αναπτύχθηκαν τόσο στο χώρο της Βιοπληροφορικής όσο και σε χώρους εκτός αυτού του ερευνητικού πεδίου. Οι αλγόριθμοι που κατασκευάσθηκαν ανήκουν κυρίως στο πεδίο της πρωτεομικής, και στοχεύουν στα προβλήματα της κατηγοριοποίησης και πρόβλεψης της λειτουργίας πρωτεϊνών, καθώς και την ομαδοποίησή τους με στόχο τον εντοπισμό μη-κανονικοτήτων σε διάφορους οργανισμούς. Τέλος, η Γενικευμένη Μεθοδολογία αξιοποιήθηκε και για την επίλυση ενός προβλήματος Υπολογιστικής Μοριακής Επιστήμης, και συγκεκριμένα στο πρόβλημα εντοπισμού μοριακών διαμορφώσεων, οι οποίες σχηματίζουν τοπολογία κόμβου στον τρισδιάστατο χώρο. Σε κάθε περίπτωση, αποδεικνύεται τόσο θεωρητικά όσο και πειραματικά, ότι η νέα προσέγγιση υπερτερεί των κλασικών προσεγγίσεων, από άποψη χρονικής επίδοσης και ευρωστίας.