Τεχνικές Κατασκευής Δένδρων Επιθεμάτων Πολύ Μεγάλου Μεγέθους Και Χρήσης Τους Για Γρήγορη Αναζήτηση Βιολογικών Δεδομένων

Abstract

Τα δένδρα επιθεμάτων χρησιμοποιούνται ευρύτατα ως ευρετήρια για ακολουθίες βιολογικών δεδομένων. Τα τελευταία χρόνια παρατηρείται πολύ μεγάλη αύξηση του όγκου αυτού του τύπου δεδομένων λόγω της συνεχούς μείωσης του κόστους για ακολουθιοποίηση του γενετικού υλικού. Το γεγονός αυτό δημιουργεί την ανάγκη για αποδοτικούς τρόπους κατασκευής των δένδρων επιθεμάτων στον δίσκο, αφού τα ευρετήρια για ακολουθίες πολύ μεγάλου μεγέθους δεν χωρούν στην διαθέσιμη μνήμη. Στα πλαίσια της διπλωματικής (α) μελετήσαμε τους κυριότερους αλγορίθμους που έχουν προταθεί για την λύση του προβλήματος και (β) υλοποιήσαμε σειρά γνωστών αλγορίθμων που χρησιμοποιούν δένδρα επιθεμάτων πάνω σε μεγάλου μεγέθους δένδρα που κατασκευάστηκαν από αυτούς τους αλγορίθμους. Για το σκοπό αυτό χρησιμοποιήσαμε και επεκτείναμε την ανοιχτού κώδικα υλοποίηση του αλγορίθμου TRELLIS (ο οποίος είναι ο πιο γρήγορος από τους αλγορίθμους που έχουν προταθεί). Τα πειράματά μας αποκαλύπτουν τη συμπεριφορά των δένδρων μεγάλου μεγέθους όταν χρησιμοποιούνται από τους αλγορίθμους που υλοποιήσαμε.