Basic Applied Bioinformatics

CHAPTER 9Needleman–Wunsch Algorithm (Global Alignment)

CS Mukhopadhyay and RK Choudhary

School of Animal Biotechnology, GADVASU, Ludhiana

9.1 INTRODUCTION

The Needleman–Wunsch algorithm (NWA; Needleman and Wunsch, 1970) is used for global alignment. We compare homologous molecular sequences character by character to achieve sequence alignment. Global alignment is the end‐to‐end alignment between two sequences; hence, it introduces gaps that represent insertions/deletions. This is useful for identifying “InDels” (Insertion and Deletions), and for overall comparison of two or more comparable (i.e., similar) sequences. Phylogenetically close sequences of the same length are the most suited for global alignment.

The best alignment can be identified by quantifying or scoring the possible alternative alignments. Scoring matrices are used to award the match(es) and penalize the mismatch(es) and gap(s), so that the best alignment with the highest score can be identified. The scores in the matrix are integer values (e.g., +1, 0, –1).

Dynamic Programming (DP) means that the scores of the subsequent cells can only be determined if the initial cells (towards the top left) have been scored. The DP methodology requires computation of the initial values (at the left and top side of the matrix) to obtain the later values of the cells (located towards the right and bottom side) in the matrix.

9.2 OBJECTIVE

To align two comparable sequences (nucleotide or amino acid) for obtaining a global ...