Λεπτομέρειες

ΕίδοςΔιπλωματική
ΚωδικόςDIPL-2009-11
ΤίτλοςΤεχνικές κατασκευής δένδρων επιθεμάτων πολύ μεγάλου μεγέθους και χρήσης τους για γρήγορη αναζήτηση βιολογικών δεδομένων
ΣυγγραφέαςΒασίλειος Πολυχρονόπουλος
Έτος2009
Λέξεις κλειδιάDNA, παραγωγή ευρετηρίων για ακολουθίες, βιολογικά δεδομένα, δένδρα επιθεμάτων, εξωτερική μνήμη, κατώτατος κοινός πρόγονος, υβριδικός δυναμικός προγραμματισμός
ΠερίληψηΤα δένδρα επιθεμάτων χρησιμοποιούνται ευρύτατα ως ευρετήρια για ακολουθίες βιολογικών δεδομένων. Τα τελευταία χρόνια παρατηρείται πολύ μεγάλη αύξηση του όγκου αυτού του τύπου δεδομένων λόγω της συνεχούς μείωσης του κόστους για ακολουθιοποίηση του γενετικού υλικού. Το γεγονός αυτό δημιουργεί την ανάγκη για αποδοτικούς τρόπους κατασκευής των δένδρων επιθεμάτων στον δίσκο, αφού τα ευρετήρια για ακολουθίες πολύ μεγάλου μεγέθους δεν χωρούν στην διαθέσιμη μνήμη. Στα πλαίσια της διπλωματικής (α) μελετήσαμε τους κυριότερους αλγορίθμους που έχουν προταθεί για την λύση του προβλήματος και (β) υλοποιήσαμε σειρά γνωστών αλγορίθμων που χρησιμοποιούν δένδρα επιθεμάτων πάνω σε μεγάλου μεγέθους δένδρα που κατασκευάστηκαν από αυτούς τους αλγορίθμους. Για το σκοπό αυτό χρησιμοποιήσαμε και επεκτείναμε την ανοιχτού κώδικα υλοποίηση του αλγορίθμου TRELLIS (ο οποίος είναι ο πιο γρήγορος από τους αλγορίθμους που έχουν προταθεί). Τα πειράματά μας αποκαλύπτουν τη συμπεριφορά των δένδρων μεγάλου μεγέθους όταν χρησιμοποιούνται από τους αλγορίθμους που υλοποιήσαμε.
ΚατηγορίαAdvanced Query Processing-Optimization Techniques
Αρχείο Επισκόπηση


Επιστροφή στην αρχική σελίδα