LinearFold — это алгоритм и набор программ для предсказания вторичной структуры РНК, обеспечивающий линейную по времени и памяти работу. Разработанный с использованием динамического программирования в направлении 5'→3' и эвристики beam search, LinearFold представляет собой эффективное решение для анализа длинных РНК-последовательностей, таких как 16S и 23S рРНК, а также для предсказания дальних пар оснований, расположенных более чем на 500 нуклеотидов друг от друга.
В отличие от традиционных методов, таких как алгоритм Нуссинова, которые имеют кубическую сложность O(n³), LinearFold использует модификацию динамического программирования, позволяющую обрабатывать последовательности за время O(n) при использовании эвристики beam search. Это делает его особенно полезным для анализа геномов вирусов с большими РНК, таких как коронавирусы, где традиционные методы могут быть слишком медленными.
- Линейная сложность: Обеспечивает предсказание структуры РНК за время O(n) и память O(n), что значительно ускоряет процесс по сравнению с традиционными методами.
- Использование 5'→3' динамического программирования: Алгоритм обрабатывает последовательность РНК слева направо, что позволяет эффективно применять эвристику beam search.
- Поддержка различных моделей энергии: Включает как термодинамические модели, так и модели, обученные с использованием машинного обучения, для более точного предсказания структуры.
- Высокая точность на длинных последовательностях: Особенно эффективен при анализе длинных РНК, таких как 16S и 23S рРНК, а также при предсказании дальних пар оснований.
- Поддержка различных режимов предсказания: Включает режимы минимальной свободной энергии (MFE), максимальной ожидаемой точности (MEA), ThreshKnot и стохастического семплинга.
- Интерактивный веб-сервис: Доступен веб-интерфейс для удобного использования алгоритма без необходимости установки программного обеспечения.
- Открытый исходный код: Исходный код доступен на GitHub, что позволяет исследователям адаптировать и интегрировать алгоритм в свои проекты.