В чем разница между глобальным и локальным выравниванием?

Глобальное выравнивание (Нидлмана-Вунша) выравнивает две последовательности от начала до конца и подходит, когда они имеют схожую длину и, как ожидается, связаны по всей длине. Локальное выравнивание (Смита-Ватермана) находит наилучшую совпадающую подобласть и подходит, когда только части последовательностей схожи, например, консервативный домен в более крупных последовательностях.

Является ли выравнивание последовательностей тем же самым, что и наибольшая общая подпоследовательность?

Они тесно связаны. Наибольшая общая подпоследовательность является частным случаем выравнивания с определенной системой оценки (совпадения вознаграждаются, разрывы бесплатны, несовпадения не допускаются). Общее выравнивание использует более богатую систему оценки со стоимостью замещений и штрафами за разрывы, но оба решаются с помощью одного и того же типа рекуррентного соотношения динамического программирования.

Алгоритмы выравнивания последовательностей

Алгоритмы выравнивания последовательностей измеряют и отображают сходство между двумя строками, находя наименее затратный способ преобразования одной строки в другую с использованием динамического программирования для операций вставки, удаления и замены.

Найти тему в PaperMindСкороFind papers & topics

Tools & resources

Скачать слайды

Learn & explore

ВидеоСкоро

Definition

Выравнивание последовательностей — это расположение двух (или более) строк для максимизации их соответствия путем вставки разрывов и сопоставления, несопоставления или замены символов; алгоритм выравнивания вычисляет оптимальное выравнивание и его оценку в соответствии с заданной моделью затрат или оценки, обычно с помощью динамического программирования.

Scope

Эта тема охватывает алгоритмы динамического программирования для сравнения строк: расстояние редактирования (Левенштейна) и наибольшую общую подпоследовательность, глобальное выравнивание (Нидлмана-Вунша), локальное выравнивание (Смита-Ватермана), а также схемы оценки (штрафы за разрывы, матрицы замещений), которые формируют биологические выравнивания. В ней рассматриваются основные рекуррентные соотношения и их квадратичная сложность по времени и пространству, а также усовершенствования для экономии памяти. Методы, основанные на индексах, и методы точного совпадения рассматриваются в связанных темах.

Core questions

Как количественно определяется сходство между двумя строками в виде расстояния редактирования или оценки выравнивания?
Как таблица динамического программирования вычисляет оптимальное выравнивание?
Что отличает глобальное выравнивание от локального выравнивания и когда каждое из них уместно?
Как штрафы за разрывы и матрицы замещений влияют на результирующее выравнивание?
Как можно уменьшить квадратичные требования к памяти для длинных последовательностей?

Key concepts

расстояние редактирования (Левенштейна)
наибольшая общая подпоследовательность
глобальное выравнивание
локальное выравнивание
алгоритм Нидлмана-Вунша
алгоритм Смита-Ватермана
штрафы за разрывы
матрицы замещений

Key theories

Глобальное выравнивание с помощью динамического программирования: Алгоритм Нидлмана-Вунша заполняет таблицу динамического программирования, записи которой дают наилучшую оценку выравнивания префиксов строк, что приводит к оптимальному сквозному (глобальному) выравниванию двух последовательностей за время, пропорциональное произведению их длин.
Локальное выравнивание для общих подпоследовательностей: Алгоритм Смита-Ватермана модифицирует рекуррентное соотношение, чтобы выравнивания могли начинаться и заканчиваться в любом месте, находя область с наивысшей оценкой совпадения (локальное выравнивание), что важно для обнаружения консервативных фрагментов в иначе несхожих последовательностях.

Clinical relevance

Выравнивание последовательностей является краеугольным камнем вычислительной биологии, используемым для сравнения последовательностей ДНК, РНК и белков с целью определения гомологии, эволюционных выводов и поиска в базах данных (эвристический алгоритм BLAST основан на локальном выравнивании). Вне биологии тот же механизм расстояния редактирования используется для проверки орфографии, нечеткого сопоставления текста, сравнения версий в системах контроля версий, а также для сравнения речи и почерка.

History

Левенштейн ввел расстояние редактирования в 1965 году. Нидлман и Вунш представили первый алгоритм глобального выравнивания белков с использованием динамического программирования в 1970 году, а Смит и Ватерман ввели локальное выравнивание в 1981 году. Метод Хиршберга с линейным использованием памяти (1975) и более поздние эвристические методы, такие как BLAST, расширили применение выравнивания до крупномасштабного практического использования.

Key figures

Saul Needleman
Christian Wunsch
Temple Smith
Michael Waterman
Vladimir Levenshtein

Seminal works

needleman1970
smith1981
gusfield1997

Frequently asked questions

В чем разница между глобальным и локальным выравниванием?: Глобальное выравнивание (Нидлмана-Вунша) выравнивает две последовательности от начала до конца и подходит, когда они имеют схожую длину и, как ожидается, связаны по всей длине. Локальное выравнивание (Смита-Ватермана) находит наилучшую совпадающую подобласть и подходит, когда только части последовательностей схожи, например, консервативный домен в более крупных последовательностях.
Является ли выравнивание последовательностей тем же самым, что и наибольшая общая подпоследовательность?: Они тесно связаны. Наибольшая общая подпоследовательность является частным случаем выравнивания с определенной системой оценки (совпадения вознаграждаются, разрывы бесплатны, несовпадения не допускаются). Общее выравнивание использует более богатую систему оценки со стоимостью замещений и штрафами за разрывы, но оба решаются с помощью одного и того же типа рекуррентного соотношения динамического программирования.