Il semplice algoritmo schematizzato nella figura consente di valutare tutti gli allineamenti tra due sequenze e di calcolarne i rispettivi punteggi, purché le sequenze siano mantenute ininterrotte, cioè siano prive di gap. L’algoritmo comporta lo scorrimento di una sequenza sull’altra e il conteggio del numero di lettere appaiate esattamente. L’allineamento numero 5 risulta migliore, con quattro appaiamenti esatti. Il concetto di miglior allineamento è comunque relativo al criterio usato per valutare la similarità.
Vince l’alineamento con il maggior numero di match.
Fra due sequenze di lunghezza n e m il numero possibile di differenti allineamenti e’ pari a n+m-1 quando si esclude l’inserimento di gaps.
L’applicazione del semplice algoritmo illustrato nella figura precedente comporta che ad ogni avanzamento della sequenza si dovrà confrontare tutte le lettere appaiate tra le due sequenze.
Si può facilmente dimostrare che alla fine si dovranno effettuare un numero di confronti pari al prodotto delle lunghezze delle due sequenze che si vogliono allineare.
Nel nostro esempio ci sono 30 coppie di lettere appaiate: 5 x 6 = 30 (prodotto lunghezze delle due sequenze).
L’efficienza di un algoritmo in termini di tempo di esecuzione è determinata dal numero di operazioni necessarie per eseguirlo.
Nel nostro esempio si tratta di un numero di operazioni proporzionale al prodotto delle lunghezze, e ciò si indica con la notazione O(nm). Se si suppone che le lunghezze n e m siano dello stesso ordine di grandezza, si userà la notazione O(n).