O αλγόριθμος Needleman
Μια συστηματική έρευνα όλων των δυνατών στοιχίσεων δυο
αλληλουχιών με μήκη n και m θα απαιτούσε την εξέταση ενός
εκθετικά μεγάλου αριθμού στοιχίσεων.
O αλγόριθμος των Needleman & Wunsch (που ανήκει σε μια
κατηγορία αλγορίθμων που είναι γνωστή με το όνομα “dynamic
programming methods”), επιτρέπει την εύρεση της βέλτιστης
στοίχισης με υπολογιστικό κόστος ανάλογο του γινομένου του
μηκών των αλληλουχιών (nm). Η διαφορά ανάμεσα σε ένα
υπολογιστικό κόστος ανάλογο του (nm) και ένος εκθετικά
μεγάλου κόστους είναι τεράστια : για δυο αλληλουχίες μήκους,
π.χ.1000 χαρακτήρων, είναι η διαφορά ανάμεσα σε δευτερόλεπτα
και ώρες (εάν όχι ημέρες) υπολογισμού.