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

Я хочу вычислить оптимальное выравнивание двух аминокислотных последовательностей в соответствии со следующим определением из патента:

«Процент идентичности между двумя пептидными или нуклеотидными последовательностями является функцией количества аминокислот или нуклеотидных остатков, которые идентичны в двух последовательностях, когда было создано выравнивание этих двух последовательностей. Идентичные остатки определяются как остатки, которые являются одинакова в двух последовательностях в заданном положении выравнивания.Процент идентичности последовательностей, используемый здесь, рассчитывается из оптимального выравнивания путем деления числа идентичных остатков между двумя последовательностями на общее количество остатков в кратчайшей последовательность и умножение на 100. Оптимальное выравнивание - это выравнивание, при котором процент идентичности является максимально возможным.Гэпы могут быть введены в одну или обе последовательности в одном или нескольких положениях выравнивания для получения оптимального выравнивания.Эти пробелы затем учитываются как неидентичные остатки для расчета процента идентичности последовательности».

Реализация Needleman и Wunsch в NCBI ( https://blast.ncbi.nlm.nih.gov/Blast.cgi ) в основном работает, но не совсем. Благодаря @David и @WYSIWIG из связанной темы SE, которая предложила это ( вычисление процентной идентичности между ДНК / аминокислотной последовательностью )

Я хочу знать, есть ли способ исправить несоответствие.

например, мой тестовый пример:

Seq1: ABDE
Seq2: AAAAAAAAAAABCDE

Реализация NCBI дает следующее выравнивание, которое имеет только 3 идентичных остатка:

введите описание изображения здесь

Но не должно ли оптимальное выравнивание с 4 идентичными остатками быть возможным так:

Seq1: ----------AB-DE
Seq2: AAAAAAAAAAABCDE

Мысли? Есть ли способ настроить реализацию, чтобы получить желаемый результат? В качестве альтернативы любой другой алгоритм, который можно заставить получить это выравнивание? BLAST или вариант?

Ответы (3)

Needleman-Wunsch выполняет сквозное (глобальное) выравнивание (BLAST использует Smith-Waterman). Needle из набора инструментов EMBOSS выполняет выравнивание Needleman-Wunsch. Он сообщит о выравнивании с наивысшей оценкой. Я не уверен, какое выравнивание он сообщает, когда есть два из них с одинаковыми баллами (я не думаю, что это случайно).

Я только что попробовал ваш случай: заменить Bна, Wпоскольку первое не обозначает какую-либо конкретную аминокислоту (это неоднозначно). Это дает:

     1 ----------AW-DE      4
                 || ||
     1 AAAAAAAAAAAWCDE     15

Обратите внимание, что вы можете изменить это поведение, изменив штрафы за открытие и расширение промежутка . Вы также можете изменить штрафы за конечные промежутки (пробелы в начале или конце выравнивания, а не в середине) в Needle.

В этом случае gap-open = 10, gap-extend = 0,5, штраф в конце промежутка = false и матрица = BLOSUM62.

Для выполнения локального выравнивания вы можете использовать Smith-Waterman. Он просто выравнивает область с наивысшей оценкой и не выполняет сквозное выравнивание. В Smith-Wateman и BLAST вы также можете изменить штрафы за открытие и расширение пробела , но эти алгоритмы не начинают и не заканчивают выравнивание пробелом.

Это результат Смита-Уотермана с открытием зазора = 1 и расширением зазора = 0,5 и BLOSUM62 в качестве матрицы подсчета очков.

     1  AW-D  3
        || |
    11  AWCD 14

Для получения дополнительной информации см. В чем разница между локальным и глобальным выравниванием последовательностей?

Данг. Какая удача, что я наткнулся на неправильные коды в Интернете по этой ссылке: fao.org/docrep/004/y2775e/y2775e0e.htm Там написано, что B обозначает аспарагин или аспарагиновую кислоту. Это верхняя ссылка даже в Google. А ФАО казалась авторитетным сайтом. Виноват!
@curious_cat О да, я не понимал. Кажется, Needle принимает неоднозначные коды, такие как Bи , Zно многие алгоритмы, вероятно, этого не делают (хотя я не слишком уверен в этом). В любом случае, ясно ли ваше сомнение?
Спасибо. Да, думаю, теперь понятно. Я приближаюсь к запатентованному оптимальному выравниванию, обнуляя все штрафы. Возможно, теперь я также предоставлю пользовательскую матрицу, чтобы сделать ее выравниванием 1-0 вместо матрицы функции подсчета очков, основанной на естественной склонности, такой как BLOSUM.

Это очень плохой тест.

The problem is that the sequences are too short and involve a long repetition. This means that the default gap penalties and the gap-length penalties are not applicable. They are designed to work with longer sequences, where the penalty of inserting a gap can be offset by an increase in matches. In any case you can get bad alignments at the ends of DNA sequences where the stretch of DNA that is aligned by introducing a gap is ‘off-screen’.

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

Дополнение (в тех же строках, что и при предоставлении вашей собственной матрицы): PSI-BLAST выполняет расчет матрицы оценок для конкретной позиции с использованием совпадений гомологов. С каждой итерацией хиты должны становиться лучше. Это своего рода машинное обучение; не очень нравится создавать свою собственную матрицу, но она принимает во внимание некоторую биологию.
Как вы говорите, это немного другое. Это стандарт для MSA (множественное выравнивание последовательностей) — по крайней мере, Clustal делает то же самое. Но ключевым моментом является обдумывание алгоритма и предположений, что, очевидно, сложно для новичка.

Ваша догадка сделана без знания вероятностей белковых замен.

Оптимальность выравнивания в BLAST — это метрика оценочной функции. Функция подсчета очков зависит от размера слова (длины начального числа, которое инициирует выравнивание), вознаграждений и штрафов за совпадения и несоответствия, стоимости пропусков и матрицы замещения. В целом BLAST использует BLOSUM и PAM — эти матрицы основаны на эволюционных данных. Подробнее о параметрах скоринга вы могли прочитать в BLAST Help .

Вы можете точно настроить эти параметры в разделе «Параметры алгоритма» в самом низу страницы анализа. Зная параметры, вы можете решить, имеет ли смысл ваше выравнивание диких предположений или нет.

Алгоритм Нидлмана для оптимального выравнивания двух аминокислотных последовательностей
СпросиСетьПолитика конфиденциальности1y, 0v