Approximate Sequence Matching with MapReduce Full text

Δανάη Κούτρα
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
2010
Διπλωματική Εργασία
Περίληψη. Η σημασία της επεξεργασίας και ανάλυσης του γενετικού κώδικα των οργανισμών και η αναπαράσταση των βιολογικών δεδομένων σε ψηφιακή μορφή που είναι επεξεργάσιμη από τους υπολογιστές οδήγησε στη συνεργασία βιολόγων και επιστημόνων της πληροφορικής για την επίλυση διάφορα ερωτημάτων που θέτουν οι πρώτοι. Ένα από τα πιο σημαντικά προβλήματα των βιολόγων είναι η μελέτη του προσεγγιστικού ταιριάσματος ακολουθιών, δηλαδή ο εντοπισμός μικρών ακολουθιών μέσα σε ακολουθίες αναφοράς με ανοχή ενός ορίου διαφορών. Το πρόβλημα αυτό στη γενική περίπτωση είναι ιδιαίτερα απαιτητικό σε χρόνο και μνήμη και οι βιολόγοι καταφεύγουν στη χρήση προσεγγιστικών αλγορίθμων, όπως αυτοί της οικογένειας BLAST, που εντοπίζουν τα πιο σημαντικά ταιριάσματα. Ωστόσο, υπάρχουν βιολογικές εφαρμογές στις οποίες απαιτείται η εύρεση των βέλτιστων ταιριασμάτων και σε αυτές τις περιπτώσεις οι προσεγγιστικοί αλγόριθμοι δεν επαρκούν. Επιπρόσθετα, η ανάπτυξη των νέων τεχνολογιών ακολουθιοποίησης βιολογικών δεδομένων και η διενέργεια ερευνητικών έργων που αποσκοπούν στην ακολουθιοποίηση του DNA κάθε ατόμου με σχετικά μικρό κόστος (Personal Genome Project) αναμένεται να οδηγήσουν σε σημαντική αύξηση του όγκου των δεδομένων που χρησιμοποιούνται στις βιοεπιστήμες. Φαίνεται, λοιπόν, ότι για την ταχεία ανάλυση των δεδομένων αυτών η κατανομή των υπολογισμών σε πολλούς επεξεργαστές είναι αναπόφευκτη. Στόχοι της διπλωματικής εργασίας είναι: (α) η βιβλιογραφική μελέτη των βιολογικών εφαρμογών που έχουν ήδη αναπτυχθεί στο προγραμματιστικό μοντέλο MapReduce που επιτρέπει κατανεμημένο προγραμματισμό, (β) η απόκτηση τεχνογνωσίας σχετικά με το MapReduce και την πιο διαδεδομένη ανοιχτού κώδικα υλοποίηση του, το Hadoop, και (γ) η ανάπτυξη προγραμμάτων, τα οποία επιλύουν το πρόβλημα προσεγγιστικού ταιριάσματος ακολουθιών εντοπίζοντας όλα τα δυνατά ταιριάσματα, στο περιβάλλον MapReduce και η αξιολόγησή τους.