Sequence alignment, runs in your browser
Needleman Wunsch algorithm calculator: score table and alignment
This Needleman Wunsch algorithm calculator takes two sequences and your match, mismatch and gap scores, then fills the whole dynamic programming table cell by cell. It marks the traceback arrows, highlights the path that gives the best global alignment, and prints that alignment with its score. A default example, GATTACA against GCATGCU, is already worked out below. Change either sequence or any score and the table updates. Local mode gives Smith-Waterman. It runs in your browser, so nothing you type is sent to a server and it never uses a free solve.
Alignment score
4 matches, 2 mismatches, 2 gaps. 3 optimal alignments (tied).
G-ATTACA | | |.|. GCA-TGCU
2 other optimal alignments
G-ATTACA | || .|. GCAT-GCU
G-ATTACA | ||. |. GCATG-CU
| G | C | A | T | G | C | U | ||
|---|---|---|---|---|---|---|---|---|
| 0 | −1 | −2 | −3 | −4 | −5 | −6 | −7 | |
| G | −1 | 1 | 0 | −1 | −2 | −3 | −4 | −5 |
| A | −2 | 0 | 0 | 1 | 0 | −1 | −2 | −3 |
| T | −3 | −1 | −1 | 0 | 2 | 1 | 0 | −1 |
| T | −4 | −2 | −2 | −1 | 1 | 1 | 0 | −1 |
| A | −5 | −3 | −3 | −1 | 0 | 0 | 0 | −1 |
| C | −6 | −4 | −2 | −2 | −1 | −1 | 1 | 0 |
| A | −7 | −5 | −3 | −1 | −2 | −2 | 0 | 0 |
Orange cells: the main traceback path. Green cells: other tied optimal paths. Small arrows in a cell show where its value can come from: ↖ diagonal, ↑ from above, ← from the left.
Needleman Wunsch calculator online: how to use it
- Type or paste two sequences into the boxes. Only letters are kept, so spaces and dashes are ignored. Up to 30 letters each.
- Set the three scores: match (usually positive), mismatch and gap (usually negative).
- Read the alignment score and the alignment printed under the form. A vertical bar marks a match, a dot marks a mismatch and a dash marks a gap.
- Look at the table to see how the score was built. The orange cells are the traceback path, and every arrow points to a neighbour that gives the cell its value.
- Press Local (Smith-Waterman) to see the best matching region instead of the whole-sequence alignment.
The scores come from a short JavaScript function, tested against a brute-force search over every alignment of short random sequences.
Needleman Wunsch steps: initialise, fill, trace back
The Needleman-Wunsch algorithm, published in 1970 by Saul Needleman and Christian Wunsch, lines up two sequences so that the total score is as high as possible. It uses dynamic programming: the best score for two prefixes is built from the scores of slightly shorter prefixes. There are three steps.
- Initialise. Put one sequence down the side and the other across the top, with an empty first row and column. Cell (0, 0) is 0. Each step right or down in the first row and column adds one gap, so the first row is 0, g, 2g, 3g and so on, where g is the gap score.
- Fill. For each remaining cell, take the best of three options: the diagonal cell plus the match or mismatch score for the two letters; the cell above plus the gap score; or the cell to the left plus the gap score. Write the maximum and remember which options gave it.
- Trace back. Start in the bottom-right cell, whose value is the score of the best global alignment. Follow an arrow back to the top-left corner. A diagonal step writes both letters, a step up writes a letter of sequence 1 against a gap, and a step left writes a letter of sequence 2 against a gap.
Needleman Wunsch example: GATTACA against GCATGCU
The table above uses match +1, mismatch −1 and gap −1. A few cells to check against the table:
- Cell (1, 1) compares G with G. Diagonal: 0 + 1 = 1. From above: −1 − 1 = −2. From the left: −1 − 1 = −2. The maximum is 1, with a single diagonal arrow.
- Cell (1, 2) compares G with C. Diagonal: −1 − 1 = −2. From above: −2 − 1 = −3. From the left: 1 − 1 = 0. The maximum is 0, so the arrow points left.
- The last cell (7, 7) compares A with U, a mismatch. Diagonal: 1 − 1 = 0. From above: 0 − 1 = −1. From the left: 0 − 1 = −1. The best global score is 0.
The main alignment, G-ATTACA against GCA-TGCU, has four matches, two mismatches and two gaps: 4 − 2 − 2 = 0, as the corner cell says. Two other alignments reach the same score.
Reading the arrows and the tie rule
When a cell has more than one arrow, more than one choice gives the same best value. Each route from the corner back to the start is a different optimal alignment; the number under the score counts them. The main alignment printed in the result follows a fixed preference: diagonal first, then up, then left. If your course states another tie rule, look for your alignment among the others listed.
For a quick look at ties, try AAAA against AA: six optimal alignments, all scoring 0.
A second example with gaps at the ends
Try AGTACGCA against TATGC. The best global alignment places the shorter sequence inside the longer one and pays for gaps at both ends: AGTACGCA over --TATGC-, with four matches, one mismatch and three gaps, so 4 − 1 − 3 = 0.
Smith-Waterman: the local alignment version
Smith-Waterman (Temple Smith and Michael Waterman, 1981) asks which part of one sequence best matches which part of the other. Three rules change in local mode.
- The first row and column are all zeros.
- No cell can be negative. If the best option is below zero, the cell is set to 0, which means start fresh here, and it has no arrow.
- The traceback starts at the highest cell in the table, not at the corner, and stops when it reaches a 0. On a tie for highest, this calculator takes the first cell reading left to right, top to bottom.
For AGTACGCA against TATGC the local score is 3, and the local alignment is TACGC over TATGC, which uses positions 3 to 7 of the first sequence and all of the second: four matches and one mismatch.
Choosing match, mismatch and gap scores
The alignment depends on the scores. Make gaps expensive, say −5, and the best alignment avoids them; make them cheap and it inserts them freely.
Biological work often uses a substitution matrix and a larger penalty for opening a gap than extending it. Here the gap is a flat charge per position, the linear gap model most courses start with.
Common mistakes when doing it by hand
- Forgetting that, in the global version, the first row and column are multiples of the gap score, not zeros.
- Stopping the global traceback early: it ends only at cell (0, 0).
FAQ
What is the Needleman-Wunsch algorithm used for?
It finds the best global alignment of two sequences, such as two DNA strands or two protein chains, by filling a table of scores and tracing back through it. Global means the alignment covers both sequences from end to end.
How does this calculator break ties?
When two or three neighbours give a cell the same best value, all of those arrows are drawn. The main alignment follows the diagonal arrow first, then up (a letter of sequence 1 against a gap), then left (a letter of sequence 2 against a gap). Other tied alignments are listed under the main one.
What is the difference between Needleman-Wunsch and Smith-Waterman?
Needleman-Wunsch aligns the two sequences end to end, and its score can be negative. Smith-Waterman never lets a cell fall below zero and starts the traceback at the highest cell, so it reports only the best matching region.
Does it support affine gap penalties or BLOSUM62?
No. This calculator uses one match score, one mismatch score and one gap score that is charged for every gap position. It is meant for learning and checking homework.
Are my sequences uploaded anywhere?
No. The alignment is computed by JavaScript on this page, and nothing is sent to Solvecam or anyone else. The sequences are gone when you close or reload the tab.