Efficient algorithms and architectures for protein 3-D structure comparison

Abstract

Protein Structure Comparison (PSC) is a well developed field of computational proteomics with active interest since it is widely used in structural biology and drug discovery. Fast increasing computational demand for all-to-all protein structures comparison is a result of mainly three factors: rapidly expanding structural proteomics databases, high computational complexity of pairwise PSC algorithms, and the trend towards using multiple criteria for comparison and combining their results (MCPSC). Despite the sustained interest in the field over the past three decades there are still open challenges in large-scale MCPSC. Firstly, its application using modern many-core and multi-core processor architectures remains unexplored. Secondly, there are few works that apply MCPSC to develop biologically relevant clusters and classify proteins. Finally, there is lack of bioinformatics software tools to support comparative analysis of large protein datasets on commodity computers.In order to address these challenges, in this thesis we have developed a software framework that exploits many-core and multi-core CPUs to implement efficient parallel MCPSC schemes in modern processors based on three popular PSC methods, namely, TMalign, CE, and USM. We evaluate and compare the performance and efficiency of two parallel MCPSC implementations using Intel’s experimental many-core Single-Chip Cloud Computer (SCC) CPU as well as Intel’s Core i7 multi-core processor. Further, we have developed a Python based utility, called pyMCPSC, allowing users to perform MCPSC efficiently, by exploiting the parallelism afforded by the multi-core CPUs of today’s desktop computers. We show how pyMCPSC, which combines five PSC methods and five different consensus scoring schemes, facilitates the analysis of similarities in protein domain datasets and how it can be easily extended to incorporate more PSC methods in the consensus scoring as they are becoming available.Experimental results from our analysis, show that the 48-core Intel SCC NoC processor is more efficient than the latest generation Core i7 CPU, achieving a speedup factor of 42 (efficiency of 0.9), making many-core processors an exciting technology for large-scale structural proteomics. We compare and contrast the performance of the two processors on several benchmark datasets and also show that MCPSC outperforms its component PSC methods in grouping related domains, achieving a high F-measure of 0.91 on the CK34 dataset. We further demonstrate using the Proteus300 dataset, that consensus MCPSC scores form a reliable basis for identifying the true classification of a protein domain, as evidenced both by ROC analysis as well as Nearest-Neighbor analysis. Structure similarity based “Phylogenetic Trees” generated by consensus scores provide insight into functional grouping within the dataset of domains. Furthermore, scatter plots generated by pyMCPSC reveal the existence of strong correlation between protein domains belonging to SCOP Class C and loose correlation between those of SCOP Class D within the Proteus dataset. Such analyses and corresponding visualizations help users quickly gain insights about their datasets. Finally we demonstrate that even very large datasets (such as SCOPCATH) can be processed and consensus scores based structural analysis carried out on readily available multi-core processors using our developed methods. pyMCPSC has been released to the proteomics community through GitHub and can be accessed at https://github.com/xulesc/pymcpsc.

Η σύγκριση πρωτεϊνών με βάση τη δομή τους (protein structure comparison, PSC) αποτελεί τομέα της υπολογιστικής πρωτεομικής με ενεργό ενδιαφέρον καθότι χρησιμοποιείται ευρέως στη δομική βιολογία και την ανακάλυψη νέων φαρμάκων. Η ταχεία αύξηση των υπολογιστικών απαιτήσεων για τη σύγκριση πρωτεϊνικών δομών είναι αποτέλεσμα τριών κυρίως παραγόντων: ταχεία επέκταση των βάσεων δεδομένων με νέες δομές πρωτεϊνών, υψηλή υπολογιστική πολυπλοκότητα των αλγορίθμων σύγκρισης δύο πρωτεινών, τάση στον τομέα για χρήση πολλαπλών μεθόδων σύγκρισης και συνδυασμό των αποτελεσμάτων τους (multicriteria PSC, MCPSC) σε ένα σκορ συναίνεσης (consensus methods). Παρά την μεγάλη πρόοδο, εξακολουθούν να υπάρχουν ανοικτές προκλήσεις στην εφαρμογή MCPSC τεχνικών σε ευρεία κλίμακα. Πρώτον, η επιτάχυνση της λειτουργίας MCPSC με τη χρήση σύγχρονων αρχιτεκτονικών επεξεργαστών πολλών πυρήνων παραμένει κατά πολύ ανεξερεύνητη. Δεύτερον, η εφαρμογή μέθόδων MCPSC στη ταξινόμηση νεων δομών πρωτεϊνών είναι περιορισμένη λόγω του υπολογιστικού κόστους και της ανάγκης χρήσης υπερυπολογιστικών δομών. Τέλος, υπάρχει έλλειψη ελεύθερα διαθέσιμων εργαλείων βιοπληροφορικής που να υποστηρίζουν τη συστηματική σύγκριτική ανάλυση και κατηγοριοποίηση μεγάλων συνόλων πρωτεϊνών με βάση τη δομή τους σε κοινούς υπολογιστές.Προκειμένου να αντιμετωπιστούν αυτές οι σημαντικές προκλήσεις, σε αυτή την διατριβή αναπτύξαμε πλαίσιο λογισμικού που εκμεταλλεύεται σύγχρονους επεξεργαστές (CPUs) για την αποδοτική υλοποίηση παράλληλων MCPSC τεχνικών βασισμένων σε τρεις δημοφιλείς μεθόδους PSC, τις TMalign, CE και USM. Συγκρίνουμε και αξιολογούμε την απόδοση και την αποδοτικότητα δύο παράλληλων υλοποιήσεων, μια για τον επεξεργαστή αρχιτεκτονικής many-core Intel Single Cloud Computer (SCC) με 48 πυρήνες οργανωμένους σε δίκτυο πλέγματος (Network on Chip), και μια και για τον γνωστό επεξεργαστή Intel Core i7 πολλαπλών πυρήνων (multi-core CPU). Επιπλέον, αναπτύξαμε Python εφαρμογή, που ονομάζεται pyMCPSC, και επιτρέπει στους χρήστες να εκτελούν εύκολα υπολογιστικά πειράματα βασισμένα σε MCPSC με μεγάλα σύνολα δεδομένων, αξιοποιώντας τον παραλληλισμό που προσφέρουν οι επεξεργαστές πολλαπλών πυρήνων των σημερινών επιτραπέζιων υπολογιστών. Δείχνουμε πώς το pyMCPSC, το οποίο συνδυάζει πέντε δημοφιλείς μεθόδους PSC για τη δημιουργία πέντε διαφορετικών σκορ συναίνεσης (consensus scores), επιταχύνει σημαντικά και διευκολύνει την συγκριτική ανάλυση μεγάλων συνόλων δεδομένων με δομές πρωτεϊνών. Επιπλέον μπορεί να επεκταθεί εύκολα ώστε να ενσωματώνει στους αλγόριθμους συναίνεση και νέες μεθόδους PSC που μπορεί να προταθούν μελλοντικά καθώς ο τομέας εξελίσσεται.Τα αποτελέσματα συγκριτικής ανάλυσής δείχνουν ότι ο επεξεργαστής Intel SCC με 48 πυρήνες (Network on Chip) είναι πιο αποδοτικός από την τελευταίας γενιάς Core i7 CPU, επιτυγχάνοντας συντελεστή επιτάχυνσης 42 (απόδοση 0,9), και καθιστώντας τους επεξεργαστές αρχιτεκτονικής many-core τεχνολογία επιλογής για την υπολογιστική δομική πρωτεομική μεγάλης κλίμακας. Επιπλέον, δείχνουμε ότι το MCPSC ξεπερνά τις μεθόδους PSC στις οποίες στηρίζεται ως προς την επιτυχία της ομαδοποίησης νεων πρωτεϊνών, επιτυγχάνοντας F-measure 0,91 στο σύνολο δεδομένων αναφοράς CK34. Επιπλέον, δείχνουμε, με τη χρήση του συνόλου δεδομένων Proteus300, ότι οι τεχνικές MCPSC που αναπτύχθηκαν βελτιωνουν την κατηγοριοποίηση πρωτεϊνών, όπως αυτό αποδεικνύεται τόσο από την ανάλυση ROC όσο και από την ανάλυση κοντινότερων γειτόνων (Nearest-Neighbor). Επιπλεον. τα ”φυλογενετικά δέντρα” που προκύπτουν με τη χρηση MCPSC παρέχουν χρήσιμες πληροφορίες και σχετικά με τη πιθανή λειτουργικότητα νεων πρωτεϊνών. Τέλος, η συγκριτική ανάλυση αναδεικνύει την ύπαρξη ισχυρής συσχέτισης πρωτεϊνικών δομών της κατηγορίας SCOP class C και χαλαρής συσχέτισης μεταξύ εκείνων της κατηγορίας SCOP class D (Proteus300). Τέτοιου είδους ενδελεχείς αναλύσεις δεδομένων και οι αντίστοιχες οπτικοποιήσεις που τις συνοδεύουν βοηθούν τους χρήστες να εξερευνούν και να εξάγουν γνώση από σύνολα δεδομένων που αναλύουν, όσο μεγάλα κι αν είναι αυτά. Δειχνουμε ότι ακόμη και σε πολύ μεγάλα σύνολα δεδομένων, με χιλιάδες domains (όπως το SCOPCATH), μπορεί να εφαρμοστεί αποδοτικά MCPSC επεξεργασία προκειμένου να διερευνηθεί η εσωτερική δομή τους, αξιοποιώντας τους επεξεργαστές πολλών πυρήνων που υπάρχουν σήμερα στους ατομικούς υπολογιστες. Το pyMCPSC που υλοποιεί παράλληλα όλη την υπολογιστική ροή (pipeline) που αξιοποιεί μεθόδους MCPSC οι οποίες αναπτύχθηκαν σε αυτή την διδακτορική διατριβή διατίθεται ελεύθερα στη επιστημονική κοινότητα στο σύνδεσμο https://github.com/xulesc/pymcpsc.