Pretend that I am a world-class expert at the subject of bioinformatics (e.g., I

Question

Pretend that I am a world-class expert at the subject of bioinformatics (e.g., I know all about alignments, and algorithms, and scoring, etc.), but yet somehow I knew nothing about the Needleman-Wunsch algorithm (as if that were possible! Maybe I'm from an alternate universe or something). Describe for me what Needleman-Wunsch is in general, what it does in particular, and what it can do for me. Like, when should I use it? When would I be better off not to use it, and should use something else instead? Notably, what are the key concepts that distinguish it from all other bioinformatics algorithms?

Explanation / Answer

The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences.

It was one of the first applications of dynamic programming to compare biological sequences.

The algorithm essentially divides a large problem (e.g. the full sequence) into a series of smaller problems and uses the solutions to the smaller problems to reconstruct a solution to the larger problem. It is also sometimes referred to as the optimal matching algorithm and the global alignment technique.

This algorithm can be used for any two strings. This guide will use two small DNA sequences as examples as shown in the diagram:

GCATGCU

GATTACA

Constructing the grid

First construct a grid such as one shown in Figure 1 above. Start the first string in the top of the third column and start the other string at the start of the third row. Fill out the rest of the column and row headers as in Figure 1. There should be no numbers in the grid yet.

G C A T G C U

G

A

T

T

A

C

A

Choosing a scoring system

Next, decide how to score each individual pair of letters. Just by looking at our two strings one may be able to see one possible best alignment:

GCATG-CU

G-ATTACA

One can see that letters may match, mismatch, be deleted or inserted (indel):

Match: The two letters at the current index the same.

Mismatch: The two letters at the current index are different.

Indel (INsertion or DELetion): The best alignment involves one letter aligning to a gap in the other string.

There are various ways to score these three scenarios. These have been outlined in the Scoring systems section below. For now the simple system used by Needleman and Wunsch will be used; matches are given +1, mismatches are given 1 and indels are given -1.

The Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance.

Stereo matching is an essential step in the process of 3D reconstruction from a pair of stereo images. When images have been rectified, an analogy can be drawn between aligning nucleotide and protein sequences and matching pixels belonging to scan lines, since both tasks aim at establishing optimal correspondence between two strings of characters. The ‘right’ image of a stereo pair can be seen as a mutated version of the ‘left’ image: noise and individual camera sensitivity alter pixel values (i.e. character substitutions); and different view angle reveals previously occluded data and introduces new occlusions (i.e. insertion and deletion of characters). As consequence, minor modifications of the Needleman–Wunsch algorithm make it suitable for stereo matching.Although performances in terms of accuracy are not state-of-the-art, the relative simplicity of the algorithm allows its implementation on embedded systems.

Although in many applications image rectification can be performed, e.g. by camera resectioning or calibration, it is sometimes impossible or impractical since the computational cost of accurate rectification models prohibit their usage in real-time applications. Moreover, none of these models is suitable when a camera lens displays unexpected distortions, such as those generated by raindrops, weatherproof covers or dust. By extending the Needleman–Wunsch algorithm, a line in the ‘left’ image can be associated to a curve in the ‘right’ image by finding the alignment with the highest score in a three-dimensional array (or matrix). Experiments demonstrated that such extension allows dense pixel matching between unrectified or distorted images.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.