О мерах сходства расположения компонентов в массивах естественно упорядоченных данных
Ключевые слова:
знаковая последовательность, информационная цепь, строй цепи, глубина строя, средняя удаленность, нуклеотидная последовательность, меры сходства-расхождения, матрица сходства, alignment-free genome comparison, межнуклеотидное расстояниеАннотация
В настоящее время не используются адекватные математические средства для анализа расположения компонентов в массивах естественно упорядоченных данных различной природы, в том числе – слов или букв в текстах, нотных знаков в записях музыкальных произведений, символов в знаковых последовательностях, данных мониторинга, чисел, отображающих упорядоченные результаты измерений, компонентов в генетических текстах. Поэтому затруднены или невозможны измерение и сравнение порядка следования сообщений, выделенных в длинных информационных цепях. Основные подходы при сравнении символьных последовательностей используют вероятностные модели и статистический инструментарий, попарное и множественное выравнивание, позволяющее определить степень сходства цепей с помощью мер редакционного расстояния. В некотором роде экзотическим являются использование псевдоспектрального и фрактального представления символьных последовательностей. Следует особо отметить «проклятие априорного неосознаваемого знания» об очевидной упорядоченности цепи, которое широко распространено в математической лингвистике, биоинформатике (математической биологии) и других аналогичных областях науки. Отмеченные подходы почти не уделяют внимания исследованию и обнаружению закономерностей конкретного расположения всех знаков, слов, компонентов массивов данных, составляющих отдельную целостную последовательность. Объектом исследования в наших работах является специальным образом организованный числовой кортеж – расположение компонентов (строй) в символьных или числовых последовательностях. При этом в качестве основы для количественного отображения строя цепи используются интервалы между ближайшими одинаковыми её компонентами. Перемножение всех интервалов или суммирование их логарифмов позволяет получить числа, которые однозначно отображают расположение компонентов в конкретной последовательности. Эти числа, в свою очередь, позволяют получить целый набор нормированных характеристик строя, среди которых средний геометрический интервал и его логарифм. Такие характеристики на удивление точно отражают расположение компонентов в знаковых последовательностях. В данной работе представлен подход для количественного сравнения построений массивов естественно упорядоченных данных (информационных цепей) произвольной природы. Предложены меры сходства-расхождения и процедура сравнения строя цепей, основанные на выделении списка совпадающих и сходных по характеристикам строя подпоследовательностей (компонентов). При этом для быстрого выделения списка совпадающих компонентов используются ранговые распределения. В работе представлен инструментарий для сравнения построений информационных цепей и продемонстрированы некоторые его возможности при исследовании строя нуклеотидных последовательностей.
Литература
2. Гусев В.Д., Косарев Ю.Г., Титкова Т.Н. Методы поиска и анализ статистических закономерностей в символьных последовательностях // Машинные методы обнаружения закономерностей: материалы всесоюзного симпозиума. 1976. С. 75–84.
3. Гусев В.Д., Куличков В.А., Никулин А.Е. Алгоритмы поиска несовершенных повторов в генетических текстах // Анализ символьных последовательностей: вычислительные системы. 1985. Вып. 113. С. 107–122.
4. Гусев В.Д., Немытикова Л.А. Векторная мера сложности нуклеотидных последовательностей // Третий сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-98). 1998. 115 с.
5. Гусев В.Д., Мирошниченко Л.А., Саломатина Н.В. Методы выделения структурных единиц в символьных последовательностях. Межъязыковые аналоги // Материалы Всероссийской конференции с международным участием «Знания-Онтологии-Теории». 2009. Т. 2. С. 53–62.
6. Беликов С.И., Гусев В.Д., Мирошниченко Л.А., Титкова Т.Н. Сравнительный анализ геномов вирусов клещевого энцефалита: дифференциация по степени вирулентности // Математическая биология и биоинформатика: IV международная конференция. 2012. С. 52–53.
7. King B.R., Aburdene M., Thompson A., Warres Z. Application of Discrete Fourier Inter-Coefficient Difference for Assessing Genetic Sequence Similarity // EURASIP Journal on Bioinformatics and Systems Biology. 2014. vol. 2014. no. 1. 8 p.
8. Srivastava S., Baptista M.S. Markovian language model of the DNA and its information content // Royal Society open science. 2016. vol. 3. no. 1. pp. 150527.
9. Nair A.S.S., Mahalakshmi T. Visualization of genomic data using inter-nucleotide distance signals // Proceedings of IEEE Genomic Signal Processing. 2005. vol. 408.
10. Afreixo V. et al. Genome analysis with inter-nucleotide distances // Bioinformatics. 2009. vol. 25(23). pp. 3064–3070.
11. Jin S. et al. A Generalized Topological Entropy for Analyzing the Complexity of DNA Sequences // PLoS One. 2014. vol. 9(2). pp. e88519.
12. Садовский М.Г. Информационно-статистический анализ нуклеотидных последовательностей: диссертация // Институт биофизики СО РАН. 2004. 394 с.
13. Amiri S., Dinov I.D. Comparison of genomic data via statistical distribution // Journal of Theoretical Biology. 2016. vol. 407. pp. 318–327.
14. Manca V., Bonnici V. InfoGenomics Tools: A Computational Suite for Informational Analyses of Genomes // Journal of Bioinformatics, Proteomics and Imaging Analysis. 2015. vol. 1. no. 1. pp. 0–0.
15. Арнольд В.И. Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств // Публичная лекция. 2006. Т. 13. 14 p.
16. Kullback S., Leibler R.A. On information and sufficiency // The Annals of Mathematical Statistics. 1951. vol. 22. no. 1. pp. 79–86.
17. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академий Наук СССР. 1965. Т. 4. С. 845–848.
18. Hamming R.W. Error detecting and error correcting codes // Bell System Technical Journal. 1950. vol. 29(2). pp. 147–160.
19. Zielezinski A., Vinga S., Almeida J., Karlowski W.M. Alignment-free sequence comparison: benefits, applications, and tools // Genome Biology. 2017. vol. 18(1). 186 p.
20. Bonham-Carter O., Steele J., Bastola D. Alignment-free genetic sequence comparisons: a review of recent approaches by word analysis // Briefings in Bioinformatics. 2014. vol. 15(6). pp. 890–905.
21. Song K. et al. New developments of alignment-free sequence comparison: measures, statistics and next-generation sequencing // Briefings in Bioinformatics. vol. 15(3). pp. 343–353.
22. Bernard G. et al. Alignment-free inference of hierarchical and reticulate phylogenomic relationships // Briefings in Bioinformatics. 2017.
23. Chan C.X., Ragan M.A. Next-generation phylogenomics // Biology Direct. 2013. vol. 8(1). pp. 3.
24. La Rosa M., Fiannaca A., Rizzo R., Urso A. Alignment-free analysis of barcode sequences by means of compression-based methods // BMC Bioinformatics. 2013. vol. 14(7). pp. S4.
25. Haubold B. Alignment-free phylogenetics and population genetics // Briefings in Bioinformatics 2013. vol. 15(3). pp. 407–418.
26. Ren J. et al. Alignment-Free Sequence Analysis and Applications // Annual Review of Biomedical Data Science. 2018. vol. 1. pp. 93–114.
27. Wang S., Tian F., Feng W., Liu X. Applications of representation method for DNA sequences based on symbolic dynamics // Journal of Molecular Structure: THEOCHEM. 2009. vol. 909. no. 1-3. pp. 33–42.
28. Salgado-Garcia R., Ugalde E. Symbolic Complexity for Nucleotide Sequences: A Sign of the Genome Structure // Journal of Physics A: Mathematical and Theoretical. 2016. vol. 49. no. 44. pp. 445601.
29. Шрейдер Ю.А., Шаров А.А. Системы и модели // М.: Радио и связь. 1982. 152 с.
30. Мазур М. Качественная теория информации // М.: Мир. 1974. 240 с.
31. Gumenjuk A., Kostyshin A., Simonova S. An approach to the research of the structure of linguistic and musical texts // Glottometrics. 2002. vol. 3. pp. 61–89.
32. Гуменюк А.С., Поздниченко Н.Н., Родионов И.Н., Шпынов С.Н. О средствах формального анализа строя нуклеотидных цепей // Математическая биология и биоинформатика. 2013. Т. 8. № 1. С. 373–397.
33. Freitas A., Afreixo V., Cruz S.E. Mixture models of geometric distributions in genomic analysis of inter-nucleotide distances // Statistics, Optimization & Information Computing Stat. 2013. vol. 1. no. 1. pp. 8–28.
34. Wasito I., Veritawati I. Fractal Dimension Approach for Clustering of DNA Sequences Based on Internucleotide Distance // IEEE 2013 International Conference of Information and Communication Technology (ICoICT). 2013. pp. 82–87.
35. Tavares A. et al. Detection of exceptional genomic words: a comparison between species // 22nd International Conference on Computational Statistics (COMPSTAT 2016). 2016.
36. Zhou L.Q., Li R., Han G.S. A Method Based on the Improved Inter-Nucleotide Distances of Genomes to Construct Vertebrates Phylogeny Tree // IEEE 2014 7th International Conference on Biomedical Engineering and Informatics. 2014. pp. 776–780.
37. Kolekar P., Kale M., Kulkarni-Kale U. Alignment-free distance measure based on return time distribution for sequence analysis: Applications to clustering, molecular phylogeny and subtyping // Molecular Phylogenetics and Evolution. 2012. vol. 65. no. 2. pp. 510–522.
38. Bonnici V., Manca V. Recurrence Distance Distributions in Computational Genomics // American Journal of Bioinformatics and Computational Biology. 2015. vol. 3. pp. 5–23.
39. Messaoudi I., Oueslati A.E., Lachiri Z. Wavelet analysis of frequency chaos game signal: a time-frequency signature of the C. elegans DNA // EURASIP Journal on Bioinformatics and Systems Biology. 2014. vol. 2014(1). pp. 16.
40. Орлов Ю.К. Частотные структуры конечных сообщений в некоторых естественных информационных системах: диссертация // Издательство Тбилисского университета. 1974.
41. Орлов Ю.К. Невидимая гармония // Число и мысль. 1980. Вып. 3. С. 70–105.
42. Кудрин Б.И. Философия техники: основания постнеклассической философии техники // М.: Техника. 2007. Вып. 36. 196 с.
43. Попова О.В., Гельфанд М.С. Существует ли аналог закона Ципфа в генетическом языке? // Научно-техническая информация. Серия 2: Информационные процессы и системы. 2000. № 4. С. 19–24.
44. Волчкова И.А., Гуменюк А.С. О мерах сходства разноязычных текстов с одинаковым содержанием. // Материалы Всероссийской конференции с международным участием «Знания – Онтологии – Теории» (ЗОНТ-13). 2013. Т. 1. С. 98–105.
45. Гуменюк А.С., Волчкова И.А. Использование средств анализа строя знаковой последовательности для формальной оценки качества перевода // Омский научный вестник. 2013. Т. 3(123). С. 251–256.
46. Шпынов С.Н., Гуменюк А.С., Поздниченко Н.Н. Применение числовой характеристики строя нуклеотидов в геномах прокариот для реклассификации внутри рода Rickettsia // Математическая биология и биоинформатика. 2016. Т. 11. № 2. С. 336–350.
47. The DDBJ/ENA/GenBank Feature Table Definition. URL: http://www.insdc.org/files/feature_table.html (дата обращения: 15.04.2018).
48. Гуменюк А.С., Поздниченко Н.Н., Шпынов С.Н. Формальный анализ строя локальной структуры нуклеотидных последовательностей // Вестник Томского государственного университета. 2014. Т. 4(29). С. 23–30.
49. GENBANK DataBase. URL: http://www.ncbi.nlm.nih.gov/nuccore/ (дата обращения: 02.03.2018).
50. Гуменюк А.С., Поздниченко Н.Н., Скиба А.А., Шпынов С.Н. Матрица сходства нуклеотидных последовательностей по их компонентам. Свидетельство о государственной регистрации программы для ЭВМ. №2017616679. 09.06.2017.
51. Поздниченко Н.Н., Гуменюк А.С., Шпынов С.Н. О картографическом представлении множества геномов прокариот с помощью числовых характеристик строя их компонентов // Новые информационные технологии в исследовании сложных структур: материалы 11-й международной конференции. 2016. С. 84–85.
Опубликован
Как цитировать
Раздел
Copyright (c) 2019 Александр Степанович Гуменюк, Артемий Андреевич Скиба, Николай Николаевич Поздниченко, Станислав Николаевич Шпынов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).