Συντάχθηκε 11-12-2013 13:10
από Eleni Stamataki
Email συντάκτη: estamataki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: σύνταξη/αποχώρηση υπάλληλος.
Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Μεταπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΔΙΑΤΡΙΒΗΣ
ΦΛΟΥΡΗ ΙΩΑΝΝΗ
με θέμα
Αλγόριθμοι Κατασκευής Δέντρων Επιθέματος
Suffix Tree Construction Algorithms
Δευτέρα 16 Δεκεμβρίου 2013, 1μμ
Αίθουσα 141.Α11 (Εργαστήριο Softnet), Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Επίκουρος Καθηγητής Αντώνιος Δεληγιαννάκης (επιβλέπων)
Καθηγητής Μίνως Γαροφαλάκης
Καθηγητής Σταύρος Χριστοδουλάκης
Περίληψη
Τα δέντρα επιθέματος χρησιμοποιούνται ευρέως για την ευρετηρίαση βιολογικών δεδομένων. Η χρήση τους είναι κρίσιμη για αλγόριθμους αναζήτησης που εφαρμόζονται στην Βιολογία. Τα τελευταία χρόνια έχει υπάρξει μια εκρηκτική αύξηση στα βιολογικά δεδομένα. Ο σκοπός αυτής της διατριβής είναι να μελετήσει τους βασικούς αλγόριθμους κατασκευής δέντρων επιθέματος και να αξιολογήσει τα πλεονεκτήματα και τις αδυναμίες τους. Μέσα από την παραπάνω μελέτη και σε συνάρτηση με την παράλληλη φύση του Hadoop Map-Reduce, προτείνεται ένας αλγόριθμος που επιχειρεί να ισορροπήσει τις απαιτήσεις ενός αλγόριθμου κατασκευής δέντρων επιθέματος στο δίσκο σε παράλληλο περιβάλλον. Τα πλεονεκτήματα της παραλληλοποίησης, του σειριακού διαβάσματος στο δίσκο και μιας πολιτικής διαβάσματος της ακολουθίας εισόδου κατέληξαν σε ένα αποδοτικό αλγόριθμο για την κατασκευή δέντρων επιθέματος για μεγάλες ακολουθίες DNA. Στα πειράματα που διενεργήθηκαν δείχνεται ότι είσοδος σε μέγεθος γονιδιώματος μπορεί να ευρετηριαστεί σε λιγότερο από 40 λεπτά, αποδεικνύοντας ότι το Hadoop Map-Reduce μπορεί να χρησιμοποιηθεί για την αποδοτική κατασκευή δέντρων επιθέματος.
Abstract
Suffix trees are widely used for indexing biological data. Their use is crucial for search algorithms applied in biology. In the past years there has been an explosive growth in biological data. The aim of this thesis is to study the main algorithms proposed over the years for constructing suffix trees and evaluate both their advantages and bottlenecks. Through the aforementioned study and with regard to the inherit parallelism of Hadoop Map-Reduce an algorithm is proposed that balances the requirements of an out-of-core suffix tree construction algorithm in a parallel fashion. The benefits of parallelism as well as serial I/O and a cache policy for reading the input string resulted in an efficient algorithm, in both time and space, for constructing a suffix tree for large DNA sequences. In the experiments conducted it is shown that genome-scale input can be indexed in less than 40 minutes proving that Hadoop Map-Reduce can be used for efficient suffix tree construction.
