Модификация алгоритма Смита-Ватермана для локального выравнивания генетических последовательностей на основе метода окна
Екатерина Сергеевна БЕЗУГЛОВА,
Егор Михайлович ШИРЯЕВ,
Николай Николаевич КУЧЕРОВ,
Михаил Григорьевич БАБЕНКО https://doi.org/10.15514/ISPRAS-2025-37(5)-14
Аннотация
В статье представлен модифицированный алгоритм локального выравнивания генетических последовательностей, основанный на алгоритме Смита-Ватермана, с использованием метода окон и кодирования длин серий. Проведено экспериментальное сравнение производительности предлагаемого подхода с классическим алгоритмом по таким метрикам, как время выполнения, среднее и пиковое потребление памяти. Результаты демонстрируют эффективность модификации при сохранении качества выравнивания, особенно в условиях ограниченных вычислительных ресурсов. Работа имеет практическое значение для задач биоинформатики, связанных с анализом геномов, аннотированием генов и поиском гомологичных участков.
Ключевые слова
алгоритм Смита-Ватермана,
кодирование длин серий,
метод окон,
генетические последовательности,
локальное выравнивание,
биоинформатика.
При поддержке: Исследование выполнено за счет гранта Российского научного фонда № 25-71-30007, https://rscf.ru/project/25-71-30007/.
Об авторах
Екатерина Сергеевна БЕЗУГЛОВА
Северо-Кавказский федеральный университет, факультет математики и компьютерных наук имени профессора Н.И. Червякова
Россия
Россия
Окончила магистратуру по специальности «Математика и компьютерные науки» в 2023 году в Северо-Кавказском федеральном университете. В настоящее время она является аспирантом, младшим научным сотрудником научно-исследовательской лаборатории биологической и медицинской информатики медико-биологического факультета Северо-Кавказского федерального университета. Ее научные интересы: биоинформатика, анализ данных, машинное обучение, нейронные сети, облачные вычисления.
Егор Михайлович ШИРЯЕВ
Северо-Кавказский федеральный университет, факультет математики и компьютерных наук имени профессора Н.И. Червякова
Россия
Россия
Окончил магистратуру по специальности «Прикладная математика и информатика» в 2022 году в Северо-Кавказском федеральном университете. В настоящее время он является аспирантом, инженером-исследователем Департамента науки и ассистентом кафедры вычислительной математики и кибернетики Северо-Кавказского федерального университета. Его научные интересы лежат в области гомоморфных методов шифрования, нейронных сетей, сохраняющих конфиденциальность, облачных вычислений и кибербезопасности.
Николай Николаевич КУЧЕРОВ
Северо-Кавказский федеральный университет, факультет математики и компьютерных наук имени профессора Н.И. Червякова
Россия
Россия
Получил степень бакалавра по специальности «Компьютерные науки» и кандидата технических наук в Северо-Кавказском федеральном университете, Ставрополь, Россия, в 2012 и 2018 годах соответственно. С 2020 года он работает доцентом кафедры математического анализа, алгебры и геометрии Северо-Кавказского федерального университета, Ставрополь, Россия. Его научные интересы включают облачные вычисления, высокопроизводительные вычисления, системы остаточных чисел, нейронные сети и кибербезопасность.
Михаил Григорьевич БАБЕНКО
Северо-Кавказский федеральный университет, факультет математики и компьютерных наук имени профессора Н.И. Червякова
Россия
Россия
Доктор физико-математических наук, заведующий кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: облачные вычисления, высокопроизводительные вычисления, система остаточных классов, нейронные сети, криптография.
Список литературы
1. Baxevanis A.D., Bader G.D., Wishart D.S. Bioinformatics. Hoboken, NJ: John Wiley & Sons, 2020, 656 p.
2. Olson M. V. The human genome project. Proceedings of the National Academy of Sciences, 1993. Vol. 90, no. 10, pp. 4338-4344.
3. Smith T. F., Waterman M. S. Identification of common molecular subsequences. Journal of Molecular Biology, 1981, vol. 147, no. 1, pp. 195-197.
4. Flynn M. J. Some Computer Organizations and Their Effectiveness. IEEE Transactions on Computers, 1972, vol. C-21, no. 9, pp. 948–960, DOI: 10.1109/TC.1972.5009071.
5. Farrar M. Striped Smith-Waterman speeds database searches six times over other SIMD implementations. Bioinformatics, 2007, vol. 23, no. 2, pp. 156-161, DOI: 10.1093/bioinformatics/btl582.
6. Barron E. T., Glorioso R. M. A micro controlled peripheral processor. Conference record of the 6th annual workshop on Microprogramming, in MICRO 6. New York, NY, USA: Association for Computing Machinery, 1973, pp. 122-128, DOI: 10.1145/800203.806247.
7. Liu Y., Wirawan A., Schmidt B. CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinformatics, 2013, vol. 14, no. 1, p. 117, DOI: 10.1186/1471-2105-14-117.
8. Rognes T. Faster Smith-Waterman database searches with inter-sequence SIMD parallelization. BMC Bioinformatics, 2011, vol. 12, no. 1, p. 221, DOI: 10.1186/1471-2105-12-221.
9. Robinson A. H., Cherry C. Results of a prototype television bandwidth compression scheme. Proceedings of the IEEE, 1967, vol. 55, no. 3, pp. 356–364, DOI: 10.1109/PROC.1967.5493.
10. Collett D. Modelling Binary Data. 2nd ed. New York: Chapman and Hall/CRC, 2002, p. 367, DOI: 10.1201/b16654
11. Lavrov I., Maksimova L. Problems in Set Theory, Mathematical Logic and the Theory of Algorithms. Springer Science & Business Media, 2003, p. 275.
12. Sayood K. Introduction to data compression. Morgan Kaufmann, 2017, p. 735.
13. Salomon D. A concise introduction to data compression. Springer Science & Business Media, 2007, p. 305.
14. Cormen T. H., Leiserson C. E., Rivest R. L. Introduction to algorithms. MIT press, 2022, p. 1251.
15. Rissanen J., Langdon G. G. Arithmetic Coding. IBM Journal of Research and Development, 1979, vol. 23, no. 2, pp. 149-162, DOI: 10.1147/rd.232.0149.
16. Chervyakov N., Babenko M., Tchenykh A., Dvoryaninova I., Kucherov N. Towards reliable low cost distributed storage in multi-clouds. 2017 International Siberian Conference on Control and Communications (SIBCON), 2017, pp. 1-6. DOI: 10.1109/SIBCON.2017.7998476.
17. Huffman D. A. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 1952, vol. 40, no. 9, pp. 1098-1101, DOI: 10.1109/JRPROC.1952.273898.
18. Witten I. H., Neal R. M., Cleary J. G. Arithmetic coding for data compression. Commun. ACM, 1987, vol. 30, no. 6, pp. 520-540, DOI: 10.1145/214762.214771.
19. Ziv J., Lempel A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 1977, vol. 23, no. 3, pp. 337-343, DOI: 10.1109/TIT.1977.1055714.
20. Winters K. D., Owsley P. A., French C. A., Bode R. M., Feeley P. S. Adaptive data compression system with systolic string-matching logic, US5532693A, 1996.
21. Welch T. A. A Technique for High-Performance Data Compression. Computer, 1984, vol. 17, no. 06, pp. 8-19, DOI: 10.1109/MC.1984.1659158.
22. Nelson M., Gailly J. L. The data compression book 2nd edition. M & T Books, New York, NY., 1995, p. 576.
23. Gusfield D. Algorithms on Stings, Trees, and Sequences: Computer Science and Computational Biology. SIGACT News, 1997, vol. 28, no. 4, pp. 41-60, DOI: 10.1145/270563.571472.
24. Rana Y. Python: simple though an important programming language. International Research Journal of Engineering and Technology (IRJET), 2019, vol. 6. no. 2, pp. 1856-1858.
Рецензия
Для цитирования:
БЕЗУГЛОВА Е.С., ШИРЯЕВ Е.М., КУЧЕРОВ Н.Н., БАБЕНКО М.Г. Модификация алгоритма Смита-Ватермана для локального выравнивания генетических последовательностей на основе метода окна. Труды Института системного программирования РАН. 2025;37(5):183-194. https://doi.org/10.15514/ISPRAS-2025-37(5)-14
For citation:
BEZUGLOVA E.S., SHIRIAEV E.M., KUCHEROV N.N., BABENKO M.G. Modification of the Smith-Waterman Algorithm for Local Alignment of Genetic Sequences Based on the Window Method. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(5):183-194. https://doi.org/10.15514/ISPRAS-2025-37(5)-14
Послать статью по эл. почте 