Предположим, что у вас есть две реализации алгоритма Смита-Уотермана (с любой эвристикой, которую они применяют для ускорения) для локального выравнивания геномных последовательностей.
Я хотел бы знать, можно ли быть уверенным, что эти реализации хорошо справляются с выравниванием (т.е. программа написана правильно). Как я могу сравнить это?
Есть только две возможности согласования Смита-Уотермана с заданной матрицей затрат. Это либо правильно, либо нет.
Честно говоря, что бы вы ни использовали, маловероятно, что чистая реализация Смита-Уотермана неверна. Это не так сложно, на самом деле. В Smith-Waterman есть много эвристических улучшений, но если вы оба а) уверены, что не хотите их тестировать б) уверены, что они не используются, вы всегда можете сгенерировать множество случайных последовательностей и выровнять их. в парах. Если какая-либо пара не соответствует одному и тому же результату таким же образом, что-то не так, и вам следует продолжить расследование.
Я полагаю, что технически на ваш вопрос можно ответить только на Stack Exchange в области вычислительной техники. Прагматичный ответ биологии таков: проблемы нет. Это настолько хорошо зарекомендовавший себя алгоритм, что его реализация на любом авторитетном сайте или у любого авторитетного поставщика, скорее всего, будет приемлемой. Никакой эвристики не задействовано, поэтому, если вы сравните разные реализации, вы должны получить похожие ответы. Я говорю похожие, а не идентичные, потому что может быть более одного сопоставления с одним и тем же баллом, но выбрано только одно. Как правило, нет никакой разницы.
Я предполагаю, что есть один аспект алгоритма Смита-Уотермана, который может различаться в разных реализациях, но именно за него вы, пользователь, несете полную ответственность — система подсчета очков. Ваше основное предположение заключается в том, что две последовательности связаны, и вы просите программу дать вам попарное выравнивание, которое «лучше всего» выражает эту связь. «Лучший» в программе означает наивысший балл по системе, которая присваивает различное значение выравниванию различных пар всех 20 аминокислот (матрица сравнения для белков) и наказывает за введение пробела (чтобы учесть вставка или удаление) и расширение однажды введенного пробела.
Какие у вас есть варианты и когда может возникнуть необходимость их реализовать? Вы можете выбирать из различных сравнительных матриц, полученных путем выравнивания блоков последовательностей одного и того же белка в организмах с разным эволюционным разделением. Эти матрицы отличаются тем, что для замены одних аминокислот требуется замена только одного основания в кодоне, тогда как для других требуются изменения во всех трех положениях кодона. Последние менее вероятны в короткие промежутки времени эволюции (например, между мышью и крысой), чем в более длинные (например, между мышью и бактерией). Поэтому в идеале вы должны использовать матрицу сравнения, наиболее подходящую для сравниваемых последовательностей.
Обстоятельства, при которых вы можете захотеть изменить штрафы за пробел или даже настроить сравнительные таблицы, по общему признанию, эзотеричны, но я бы посоветовал лучше подумать о применимости системы подсчета очков к вашей биологической проблеме, чем беспокоиться о том, что кто-то может сделал хеш реализации компьютерного алгоритма.
АлисаД
Дэйвид
Максим Кулешов
WYSIWYG