BioinformaticsLesson 2 of 4 in the course Sequence alignment

Needleman–Wunsch Global Alignment: Scoring, Traceback, and Complexity

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

The Needleman–Wunsch algorithm finds an optimal global alignment between two sequences. This lesson introduces the problem it solves, the kinds of pairings an alignment can contain, and how a scoring system ranks candidate alignments.

Needleman–Wunsch compares two strings, commonly DNA, RNA, or protein sequences. A global alignment aims to align the sequences from beginning to end, allowing gaps when they help produce a better overall correspondence. The algorithm was developed by Saul B. Needleman and Christian D. Wunsch and published in 1970. It applies dynamic programming: it breaks a larger problem into smaller prefix-alignment problems and reuses their solutions.

All flashcards

What is a global alignment?
An end-to-end alignment of two sequences that pairs their positions from beginning to end, inserting gaps where needed.
What is an indel in an alignment?
An insertion or deletion represented by aligning a letter in one sequence with a gap in the other.
What is the purpose of the Needleman–Wunsch algorithm?
To find the optimal end-to-end alignment of two sequences under a specified scoring system.
What are the three basic alignment events?
A match (identical letters), a mismatch (different letters), and an indel (a letter aligned to a gap).
How is an alignment’s score calculated?
Add the scoring value for every aligned position, using the selected values for matches, mismatches, and gaps.

Quiz questions

  1. What type of alignment does the Needleman–Wunsch algorithm optimize?Answer: A global alignment spanning both sequences.
  2. What alignment event is called an indel?Answer: A character aligned with a gap in the other sequence.
  3. Under match +1+1, mismatch −1-1, and indel −1-1, what is the score of four matches and four penalized positions?Answer: 4(1)+4(−1)=04(1)+4(-1)=0.
  4. Why can different scoring schemes rank candidate alignments differently?Answer: They assign different values to aligned pairs and gaps.
  5. How can a scoring scheme penalize gaps more strongly than mismatches?Answer: Give gaps a more negative score than mismatches.

Based on the Wikipedia article Needleman–Wunsch algorithm, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Bioinformatics

All Bioinformatics lessons
BioinformaticsBiological Databases: Data Types, Integration, and Specialized Resources5 flashcards · 5 quiz questions · 4 gamesPlay free →BioinformaticsHuman Genome Project: Sequencing, Collaboration, and Reference Completion5 flashcards · 5 quiz questions · 4 gamesPlay free →BioinformaticsGenBank: Submissions, Records, and Critical Use5 flashcards · 5 quiz questions · 4 gamesPlay free →BioinformaticsPhylogenetic Inference: Trees, Methods, Classification, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →BioinformaticsSmith–Waterman Local Alignment: Scoring, Traceback, and Efficiency5 flashcards · 5 quiz questions · 4 gamesPlay free →BioinformaticsBLAST: Algorithms, Search Programs, Statistics, and Result Interpretation5 flashcards · 5 quiz questions · 4 gamesPlay free →