.
Ο αλγόριθμος Needleman-Wunsch είναι ένας αλγόριθμος που χρησιμοποιείται για ολική στοίχιση ακολουθιών. Συγκεκριμένα χρησιμοποιείται για να υπολογιστεί η βέλτιστη ολική στοίχιση μεταξύ δύο ακολουθιών - συμβολοσειρών, μια διαδικασία ιδιαίτερα χρήσιμη σε διάφορους τομείς, όπως για παράδειγμα στη βιοπληροφορική. Ο συγκεκριμένος αλγόριθμος ανήκει στη φιλοσοφία αλγορίθμων δυναμικού προγραμματισμού.
Περιγραφή του αλγορίθμου Needleman-Wunsch
Στον πυρήνα του αλγορίθμου Needleman-Wunsch για ολική στοίχιση ακολουθιών υπάρχει ένας πίνακας του οποίου οι γραμμές αντιστοιχούν στα σύμβολα της μίας ακολουθίας και οι στήλες στα σύμβολα της άλλης. Κάθε κελλί αυτού του πίνακα αντιστοιχεί σε ένα ταίριασμα γραμμάτων των δύο ακολουθιών, και περιέχει δύο τιμές: Ένα σκορ (που υπολογίζεται με βάση ένα συγκεκριμένο σχήμα) και έναν δείκτη (του οποίου η χρήση γίνεται πιο σαφής παρακάτω). Κατά την εκτέλεση ακολουθείται μια αλληλουχία τριων φάσεων: 1. Αρχικοποίηση πίνακα, 2. Γέμισμα πίνακα και 3. Οπισθοχώρηση (traceback). Στις επόμενες ενότητες αναλύονται καθεμία από αυτές τις φάσεις.
Αρχικοποίηση πίνακα
Σε αυτή τη φάση προσδίδονται τιμές στην πρώτη γραμμή και στην πρώτη στήλη του πίνακα. Αυτό υπονοεί ότι για κάθε κελλί της πρώτης γραμμής και της πρώτης στήλης του πίνακα γίνονται δύο αναθέσεις: Ανατίθεται ένα σκορ και ένας δείκτης.
Γέμισμα πίνακα
Σε αυτή τη φάση γεμίζονται τα κελλιά του πίνακα με τιμές. Σε αυτήν την φάση σε κάθε κελλί του πίνακα ανατίθεται ένα σκορ και ένας δείκτης. Αυτή η ανάθεση γίνεται με βάση τις τιμές των γειτόνων του κελλιού του πίνακα.
Οπισθοχώριση
Σε αυτή τη φάση ανατρέχουμε τον πίνακα προς τα πίσω για να βρούμε την επιθυμητή στοίχιση.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
