LinearPartition — это алгоритм для приближённого расчёта партиционной функции и вероятностей спаривания оснований РНК с линейной временной сложностью. Он был разработан для ускорения предсказания вторичной структуры РНК, особенно для длинных последовательностей, где традиционные методы, такие как Vienna RNAfold, становятся вычислительно затратными. Алгоритм был представлен в статье, опубликованной в журнале Bioinformatics в 2020 году.
Основной идеей LinearPartition является использование эвристического подхода, вдохновлённого техниками инкрементального анализа контекстно-свободных грамматик. Это позволяет значительно ускорить расчёты по сравнению с классическими методами динамического программирования, сохраняя при этом приемлемую точность предсказаний. Например, на последовательности длиной 32 753 нуклеотида LinearPartition выполняет расчёты за 1,3 минуты, в то время как Vienna RNAfold требует около 2,5 дней.
- Линейная временная сложность: позволяет эффективно обрабатывать длинные РНК-последовательности.
- Приближённый расчёт партиционной функции: оценивает ансамбль возможных структур РНК.
- Расчёт вероятностей спаривания оснований: предоставляет информацию о вероятности образования пар оснований в различных участках молекулы.
- Улучшенная точность на длинных последовательностях: особенно эффективен для предсказания структуры рРНК, где традиционные методы могут быть менее точными.
- Открытый исходный код: доступен на GitHub, что позволяет исследователям адаптировать и интегрировать алгоритм в свои проекты.