O αλγόριθμος Needleman
Η θεμελιώδης παρατήρηση στην οποία βασίζεται ο αλγόριθμος
είναι ότι οποιοδήποτε υποσύνολο της βέλτιστης στοίχισης
πρέπει επίσης να είναι βέλτιστο, ειδάλλως η στοίχιση θα
μπορούσε να βελτιστοποιηθεί και άλλο (μέσω της βελτίωσης της
Έστω, λοιπόν, μια βέλτιστη στοίχιση ανάμεσα σε ένα υποσύνολο
κ αμινοξέων από την αλληλουχία α (α1α2…ακ) και σε ένα
υποσύνολο μ αμινοξέων από την αλληλουχία β (β1β2…βμ), και
έστω ότι η τρέχουσα τιμή βαθμολογίας (αυτής της βέλτιστης
υποστοίχισης) είναι Sκ,μ .
Θέλουμε να επεκτείνουμε αυτή τη βέλτιστη υποστοίχιση κατά
μια θέση προς τα δεξιά. Υπάρχουν τρεις μόνο δυνατότητες για
να επιτευχθεί αυτή την επέκταση :