Восстановление отсутствующих данных в символьных последовательностях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Рубцов, Антон Геннадьевич

• Рубцов, Антон Геннадьевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Рубцов, Антон Геннадьевич

1. Обзор методов заполнения пропусков в данных.

1.1. Статистические методы.

1.2. Методы, основанные на моделировании.

1.3. Коды обнаружения ошибок и корректирующие коды.

1.4. Выводы.

2. Постановка задачи и критерий качества заполнения.

2.1. Постановка задачи.

2.2. Критерий качества заполнения.

2.3. Выводы.

3. Кинетическая машина Кирдина, матричное представление частотного словаря и генетические алгоритмы в задаче восстановления отсутствующих данных в символьных последовательностях.

3.1. Кинетическая машина Кирдина.

3.2. Кинетическая машина Кирдина в задаче восстановления утерянных данных.

3.3. Последовательный имитатор.

3.4. Отличие КМК от случайных процессов и классических параллельных систем вычислений.

3.5. Матричное представление частотных словарей.

3.6. Построение заполнений с помощью матричного представления частотного словаря.

3.7. Генетические алгоритмы в задаче восстановления отсутствующих данных.

3.8. Выводы.

4. Программная реализация и вычислительные эксперименты.

4.1. Эксперименты.

4.2. Выводы.

Введение диссертации (часть автореферата) на тему «Восстановление отсутствующих данных в символьных последовательностях»

Актуальность темы

Подавляющее большинство методов обработки и анализа данных работают только с полными данными. На практике очень часто встречаются ситуации, когда какая-либо часть данных отсутствует. Для того чтобы иметь возможность обрабатывать такие данные, необходимо восстановить отсутствующие. Существуют различные подходы к решению этой задачи. Большинство методов позволяют получить значения пропущенных данных исходя из принципа их максимальной похожести на полные имеющиеся данные.

При проведении статистического анализа [21, 23] на практике ограничиваются анализом не всей генеральной совокупности в целом, а лишь некоторого выборочного числа наблюдений. Анализируемая выборка должна отвечать критериям качественности и полноты. Но в ситуациях, когда некоторые свойства у исследуемых объектов отсутствуют, происходит смещение основных статистических характеристик. Например, смещения математического ожидания и дисперсии возрастают прямо пропорционально числу пропусков. То есть, ошибка напрямую зависит от количества отсутствующих данных. Причинами таких пропусков могут послужить, например, отсутствие значений вследствие каких-то мелких поломок оборудования, не связанных с экспериментальным процессом, или нежелание респондента при проведении статистического опроса отвечать на вопросы о своих доходах. Знание механизма, приводящего к отсутствию значений, является ключевым при выборе методов анализа и интерпретации результатов. Неполные данные несут в себе новую информацию для исследования, важность которой может быть велика. Поэтому ее следует включать в анализ.

Практически все методы восстановления данных используют аппарат теории вероятности и математической статистики. Как правило, подобные методы восстанавливают пропущенные данные, представленные в какой-нибудь специальной форме, например, в виде таблиц. К тому же, как говорилось ранее, эти данные должны удовлетворять критериям качественности и полноты; это достаточно жесткое ограничение для практического применения. Работы, посвященные восстановлению пропущенных данных, в основной своей массе рассматривают многомерные данные [8, 16, 17, 20, 21, 23]. В этих работах данные (объекты) представляются точкой в многомерном пространстве, а параметры объекта являются координатами этой точки. При этом для восстановления пропущенных координат зачастую требуется некоторая априорная информация.

Символьные последовательности - это классические объекты математики. Они встречаются как предмет изучения во многих прикладных задачах, от теоретического программирования и теории управления до биологии и лингвистики. Изучение символьных последовательностей позволяет ответить на множество вопросов различных областей науки, связанных с чистой или прикладной математикой.

Как объект прикладного исследования, символьные последовательности встречаются во всех областях, где рассматриваются те или иные объекты, состоящие из большого числа одинаковых фрагментов. При этом схожесть или подобие могут носить искусственный характер. Исследователь вправе по своему усмотрению рассматривать некоторые фрагменты исследуемого объекта, например, нуклеотиды в молекуле нуклеиновой кислоты или символы в текстах какого-либо естественного языка, записанные в алфавитной системе записи, как тождественные друг другу, не отличающиеся ничем, кроме своего положения в рассматриваемом объекте — символьной последовательности.

Рассмотрим биологические макромолекулы, например нуклеиновые кислоты. Они играют ключевую роль во многих процессах, протекающих в живых организмах. Изучение структуры, а также функциональных, химических, физико-химических и прочих свойств нуклеиновых кислот активно ведется специалистами различных областей науки. Одним из важных направлений является изучение нуклеиновых кислот как символьных последовательностей (нуклеотидных последовательностей). Существующие в настоящий момент методы выделения нуклеиновых кислот не дают качественного извлеченного материала. Соответственно, получаемые последовательности нуклеотидов зачастую являются неполными, что существенно затрудняет их исследование для биологов и генетиков. Поэтому возникает задача восстановления недостающих данных в таких последовательностях.

Цель работы

Целью работы является: разработка и реализация метода восстановления отсутствующих данных в символьных последовательностях, который включает в себя три алгоритма восстановления отсутствующих данных: с использованием кинетической машины Кирдина, с использованием матричного словаря и с использованием генетических алгоритмов.

Задачами работы являются: исследование свойств полученных алгоритмов; решение вопроса о существовании заполнения из слов заданного частотного словаря; оценка количества всех возможных заполнений из слов заданного частотного словаря, удовлетворяющих граничным условиям; исследование полученного метода на качество восстановления отсутствующих данных.

Научная новизна

Результаты диссертации являются новыми. В частности, разработан метод восстановления данных, который работает с символьными последовательностями, при этом их утерянные части восстанавливаются с использованием только той информации, которая содержится в самих символьных последовательностях (частотные словари). Оценка сверху числа заполнений дается выражением (N — мощность алфавита, L — длина отсутствующей части), что для алфавитов и характерных размеров пропусков, встречающихся в различных приложениях, представляет собой достаточно большую величину (порядка 1012). Таким образом, задача построения заполнения простым перебором вариантов представляется весьма ресурсоемкой. Необходим метод, снижающий вычислительные затраты. Кроме того, построение каждого из вариантов заполнений не зависит от построения других заполнений, что сделало возможным использование подходов и методов параллельных вычислений.

Одним из вариантов такого (идеального) вычислителя рассматривалось устройство, основанное на идее молекулярных вычислений - кинетическая машина Кирдина (КМК). КМК является математическим аппаратом, обеспечивающим высокий уровень распараллеливания вычислений. Тем не менее, задача физического построения такого устройства далека от разрешения, поэтому был построен имитатор КМК на обычной последовательной машине фон Неймановского типа, который необходим для решения нашей конкретной задачи, а не всех алгоритмов, которые могут быть представимы в КМК. Также, для повышения эффективности построения заполнений, последовательный имитатор КМК был модифицирован.

Однако использование КМК не решает вопрос о существовании заполнения из опорного словаря в силу своей стохастичности. В связи с этим был предложен принципиально новый подход - особое матричное представление опорного частотного словаря.

Для всякого частотного словаря возможны три (различных) матричных представления. Первое - полностью эквивалентно самому частотному словарю, второе - соответствует Марковскому процессу порядка q -1, который реализует гипотезу о наиболее вероятном продолжении слов этой длины, третье представление эквивалентно задаче определения числа маршрутов на графе, соответствующем матрице. Доказано утверждение о том, что возведение данной матрицы в соответствующую степень эквивалентно построению всех возможных заполнений из заданного опорного частотного словаря. Используя это утверждение, можно точно определить количество всех заполнений и построить их.

Следующий подход к построению заполнений также основан на идее сокращения ресурсоемкости вычислений и нахождении оптимального, с точки зрения выбранного нами критерия, заполнения. Сократить перебор можно только за счет выбора оптимальных и квазиоптимальных направлений на графе заполнений. Выбор таких направлений осуществлялся с помощью эволюционных алгоритмов оптимизации, а именно - генетических алгоритмов.

Практическая значимость

На практике методы могут применяться в задачах, которые требуют восстановления пропусков в символьных последовательностях — от теории передачи данных до молекулярной биологии. В частности, с помощью этих методов можно решить задачу восстановления недостающих элементов в нуклеотидных последовательностях. Заполнение таких пробелов осмысленной информацией может в значительной степени облегчить и продвинуть работу генетиков. Также эти методы могут применяться для восстановления пробелов в текстах естественного языка при передаче сообщений, когда сообщение доходит не полностью. Здесь сообщение может передаваться как на расстояние (связь), так и во времени - книги, тексты.

Апробация работы

Результаты работы были представлены на IX Всероссийском семинаре «Моделирование неравновесных систем - 2006», XI международной конференции «Информационные и математические технологии в научных исследованиях», XIV и XV Всероссийском семинаре «Нейроинформатика и ее приложения», V школе-семинаре «Распределенные и кластерные вычисления», международной конференции «Компьютерное моделирование и интеллектуальные системы», XII Байкальской Всероссийской конференции «Информационные и математические технологии в науке и управлении», VI и VII Всероссийских ФАМ конференциях. По теме диссертации опубликовано 15 работ.

Структура диссертации

Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы из 157 наименований, содержит 11 рисунков. Общий объем диссертации составляет 109 страниц.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Рубцов, Антон Геннадьевич

4.2. Выводы

В данной главе приведены результаты вычислительных экспериментов по восстановлению утерянных данных в символьных последовательностях. Результаты показали, что с помощью разработанных методов можно решать задачи по восстановлению данных. Эффективность каждого из методов зависит от длины лакуны и характера самих данных.

Заключение

В работе решается задача восстановления утерянных (или пропущенных) данных в символьных последовательностях, в частности, генетических последовательностях. Для восстановления таких данных используется только та информация, которая содержится в исходном тексте и доступна исследователю - частотные словари. В качестве критерия качества восстановления используется условная энтропия (мера схожести).

В работе предложено три алгоритма восстановления утерянных данных в символьных последовательностях.

Первый - с помощью кинетической машины Кирдина. Построен имитатор КМК применительно к задаче восстановления данных. Для повышения эффективности построения заполнений в символьной последовательности имитатор КМК был модифицирован. Всего было внесено три модификации:

- все заполнения росли только в одном направлении — слева направо, для определённости;

- модификации подвергся словарь, по которому строились заполнения;

- периодически проводилась селекция всех слов, являющихся продолжениями опор.

Второй подход заключается в представлении опорного частотного словаря в виде матрицы А. Рассмотрено специальное матричное представление частотного словаря. Даны определения матрицы заполнений и индикаторной матрицы. Сформулировано и доказано утверждение о том, что возведение матрицы заполнений в степень L + t эквивалентно построению всех возможных заполнений из заданного опорного частотного словаря для всех возможных опор, где L — длина лакуны, t— длина правой опоры. Получен алгоритм построения заполнений, основанный на матричном представлении частотного словаря. Получен алгоритм, с помощью которого можно за приемлемое время ответить на вопрос о существовании заполнений из опорного частотного словаря, а также определить число таких заполнений.

Третий подход - использование генетических алгоритмов. Представлена структура ГА применительно к задаче восстановления утерянных данных.

Проведены вычислительные эксперименты по заполнению лакун в символьных последовательностях. Полученные результаты показали, что каждый из предложенных методов может применяться для восстановления данных. Качество восстановления проверялось при различных значениях параметров.

Каждый алгоритм имеет свою область применения. Так имитатор КМК «хорошо» заполняет пробелы в текстах разной сложности, алфавитов различной мощности, и применим для больших лакун. Однако он не гарантирует построения оптимального заполнения. В то время как матричное представление позволяет построить все заполнения по данному словарю, но не работает на больших алфавитах и лакунах. Матричное представление лучше всего использовать для небольших (до 10 символов) лакун, когда мощность словаря не превышает 2000 слов.

ГА хорошо зарекомендовали себя при мощности словаря до 64 слов и толщине словаря 3 символа. При этом длина лакуны может достигать 50 символов.

Полученные методы зарекомендовали себя как эффективные способы восстановления утерянных или пропущенных данных в символьных последовательностях.

Таким образом, на защиту выносятся следующие положения: Разработать метод восстановления отсутствующих данных, включающий в себя:

- метод построения заполнения; критерий качества заполнения; построение заполнений с помощью кинетической машины Кирди-на и ее частного последовательного имитатора; матричное представление частотного словаря и ответ на вопрос о существовании заполнения из опорного частотного словаря; построение заполнений с помощью генетических алгоритмов;

Исследование свойств полученных алгоритмов при решении задач восстановления.

Список литературы диссертационного исследования кандидат физико-математических наук Рубцов, Антон Геннадьевич, 2010 год

1. Altschul S.F., Lipman D.J. Trees, stars and multiple biological sequence alignment//SIAM J. Appl. Math. (1986), vol. 48, 603 616.

2. Ayala F.J., Kiger, Jr. J.A. Modern Genetics// The Benjamin/ Cum-mings Pbl. Co., Inc. Menlo Park, California, 1986.

3. Banzhaf W., Francone F. D., Nordin P. «The Effect of Extensive Use of the Mutation Operator on Generalization in Genetic Programming» Department of Computer Science, Dortmund University, Germany

4. Blaisdell B.E. Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eucariotic nuclear DNA sequences protein coding and noncoding // Mol. Evol. (1985), Vol. 21, p. 278 -288.

5. Buldyrev S.V., Goldberger A.L., Havlin S., Peng С. K., Simons M., Sciortino F., Stanley H.E. Long- range power - law correlations in DNA // Phys. Rev. Letters (1993), vol. 71, p. 1776.

6. Breen S., Waterman M.S., Zhang N. Reneval theory for several patterns// J. Appl.Prob. (1985), Vol. 22, p. 228 234.

7. Brendel V., Beckmann J.S., Trifonov E.N. Linguistics of nucleotide sequences: morphology and comparison of vocabularies // J. Biomol. Struct. Dyn. (1986), Vol. 4, p. 11 22.

8. Beckmann J.S., Brendel V., Trifonov E.N. Intervening sequences exi-bit distinct vocabulary // J. Biomol.Struct.Dyn.(1986), Vol. 4, p. 391 -400.

9. Cramer Nichael Lynn «А representation for the adaptive generation of simple sequential programs» Proceedings of an International Conference on Genetic Algorithms and Their Applications. Hillsdale, NJ: Lawrence Erlbaum Associates 1985

10. Carrillo H., Lipman D.J. The multiple sequence alignment problem in biology // SIAM J. Appl. Math. (1988), vol. 48, p. 1073 1082.

11. Dayhoff J.E. Distinguished words in data sequences: Analysis and Applications to nevral coding and other fields// Bull.Math.Biol. (1984), Vol. 46, p. 529-543.

12. Deken T.G. Some limit results for longest common subsequences// Discrete Mathematics (1979), vol. 26, №1, p. 17 31.

13. Day W.H.E., Jonson D.S., Sancoff D. The computational complexity of inferring rooted phylogenies by parsimony// Math. Biosci. 1986. - v. 81. p. 33-42.

14. Findler N.V., Van Leeuwen J. A family of similarity measures between two strings// IEEE Trans, on Pattern Analysis and Machine Inteligence, (1979), vol. PAMI 1,№1, p. 116 - 118.

15. Fitch W.M., Smith T.F. Optimal sequence alignment// Proc. Natl. Acad. Sci. USA (1983), vol. 80, p. 1382 1386.

16. Finkelstein A.V., Roytberg M.A. Computation of biopolymers: a general approach to different problems. BioSystems, 1993, vol. 30 (1 1 3). ( spec, volume «Computer genetics». P.A. Pevzner, M.S. Gelfand, eds.).

17. Goad W.B., Kanehisa M.I. Pattern recognition in nucleic acid sequences//Nucleic acid reseach (1982), vol. 10, №1.

18. Goulden I.P., Jackson D.M. An inversion theorem for claster decomposition of sequences with distinguished subsequences// J. London Math.Soc.(1979), Vol. 20, p. 567 576.

19. Guibas L.J., Odlyzko A.M. String overlaps, pattern matching and non-transitive games// J. Combinatorial Theory (ser. A). (1981), p. 183 208.

20. Gardner M. On the paradoxical situations that arise from non transitive relations// Sci. Am. (1974), vol. 231, p. 679 684.

21. Gelfand M.S., Roytberg M.A. A dynamic programming algorithm for prediction of the exon intron structure. BioSystems, 1993, vol. 30 (1 — 3). (spec, volume «Computer genetics». P.A. Pevzner, M.S. Gelfand, eds.).

22. A.N. Gorban and A.Yu. Novokhodko. Neural Networks In Transposed Regression Problem, Proc. of the World Congress on Neural Networks, Sept. 15 18, 1996, San Diego, CA, Lawrence Erlbaum Associates, 1996, pp. 515 - 522.

23. Gorban A.N., Gorbunova K.O., Wunsch D.C. Liquid Brain: Kinetic Model of Structureless Parallelism // Advances in Modelling & Anal-isis.- ASME.- 2000.-V.5, №5.

24. Gorban A.N., Gorbunova K.O., Wunsch D.C. Liquid Brain: The Proof of Algorithmic Univer sality of Quasichemical Model of Fine-Grained Parallelism // Neural Network World.- 2001.-№4.- P.391 412.

25. Gorbunova E.O., Kondratenko Yu.V., Sadovsky M.G. Data loss reparation due to indeterminate fine-grained parallel computation // ICCS, LNCS 2658, Springer-Verlag, Berlin Heidelberg, 2003.- P. 794 801.

26. Goldberg D. E. «Genetic algorithms in search, optimization, and machine learning» Reading, MA: Addison-Wesley, 1989

27. Garden P.W. Markov Analysis of Viral DNA/RNA sequences// J. Theor. Biol. (1980), Vol. 82, p. 679 684.

28. Gordon, Geoffrey, System Simulation, 2nd ed., Prentice-Hall, 1978.

29. Holland J. H. «Adaptation in natural and artificial systems» Ann Arbor: University of Michigan Press, 1975

30. Hunt J.W., Szymansky T.G. A fast algorithm for computing LCS// CASM (1977), vol. 20, №5, p. 350 353.

31. Jaap P. L. Brand. Development, implementation and evaluation of multiple imputation strategies for the statistical analysis of incomplete data // Print partners ispkamp, Enschede 1999.

32. Koza John R. «Genetic programming tutorial» URL: http://www.genetic-programming.com/gpanimatedtutorial.html

33. Koza John R. «Hierarchical genetic algorithms operating on populations of computer programs» Proceedings of the 11th International Joint Conference on Artificial Intelligence. San Mateo: Morgan Kaufman, 1989

34. Koza John R. «The Genetic Programming Paradigm: Genetically Breeding Populations of Computer Programs to Solve Problems» Cambridge, MA: MIT Press, 1992

35. Koza John R. «Genetic Programming: On Programming Computer by Means of Natural Selection and Genetics» Cambridge, MA: The MIT Press, 1992

36. Kruskal J.B. An overview of sequence comparison// Siam Review Apr. (1983), Vol. 25, №2, p. 201 237.

37. Karlin S., Ghandour G., Ost F., Tavare S., Korn L. J. New approaches for computer analysis of nucleic acid sequences// Proc. Natl. Acad. Sci. USA (1983), Vol. 80, p. 5660 5664.

38. Kingman T.F.C. Subadditive ergodic theory// The Annals of Probability (1973), vol. 1, №6, p. 883 909.

39. Luo Liaafu, Li Hong The statistical correlation of nucleotides in protein coding DNA sequences // Bull. Math. Biol. (1991), vol. 53, №3, p. 345 -353.

40. Lempel A., Ziv J. On the Complexity if Finite Sequences// IEEE Trans, on Inf. Th. (1976), Vol. IT 22, №1, p. 75 - 81.

41. Law, Averill M. "Designing and Analyzing Simulation Experiments", Industrial Engineering, March 1991, pp. 20-23.

42. McGreight E.M. A space — economical suffics tree construction al-horithm// JASM (1976), v. 23, № 2, p.262 272.

43. Mirkcs E.M., Popova T.G., Sadovsky M.G. Investigating statistical properties of genetic texts: A new approach// Advances in Modeling & Analysis, ser.B, (1993) AMSE Press. Vol. 27, №1, p. 1 17.

44. Mani G.S. Correlation between coding and non — coding regions of DNA sequences // J. Theoret. Biol. 1992. v. 158, pp. 429 -445.

45. Nemenchinskaya E.O., Kondratenko Yu.V., Sadovsky M.G. Entropy based approach to data loss reparation through the indeterminate finegrained parallel computation // Open Systems & Information Dynamics.- 2004.- V.l 1, № 2.- P.161 175.

46. Needleman S.B., Wunch S. B. A general method applicable to the search for similarities in the amino acid sequences of two proteins// J. Mol. Biol. (1970), vol. 48, p. 443 453.

47. Nakatsu N., Kambayashi Y., Yalima S. A LCS algorithm suitable for similar text strings//Acta Informatica (1982), vol. 18, Fasc. 3, p. 171 -179.

48. Neelamkavil, Francis Computer Simulation and Modeling, John Wiley & Sons, 1987.

49. Poli Riccardo «Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover». — Genetic Programming and Evolvable Machines, 2, 2001.

50. Pevzner P.A., Borodovsky M.Yu., Mironov A.A. 1. The significance of deviation from mean statistical characteristics and prediction of the frequency of occurrences of words// J.Biomol. Struct.Dyn.(1989), Vol. 6, p. 1013 -1026.

51. Pevzner P.A., Borodovsky M.Yu., Mironov A.A. Linguistics of nucleotide sequences: 11. Stationary words in genetic texts and zonal structure of DNA//J. Biomol. Struct. Dyn. (1989), Vol. 6, p. 1027 -1038

52. Rossiev D.A., Savchenko A.A., Borisov A.G., Kochenov D.A. The employment of neural network classifier for diagnostics of different phases of immunodeficiency // Modeling, Measurement & Control. -1994. - V. 42. - № 2. P. 55-63.

53. Roytberg M.A. Similarity search in two biological sequences. Proceedings of the Conference «Modelling and Computer Methods in Molecular Biology and Genteics», p. 7 8, Novosibirsk, 1990.

54. Roytberg M.A. Mathematical methods of the analysis of biopolymer sequences // (S. Gindikin, ed.). AMS, 1992, Providence. P. 103 117.

55. Serre Т., Auvergne M., Goupil M. J. A new method for filling gaps in data // Astron. Astrophys. 259, p. 404 411, 1992.

56. Sellers P.H. On the theory and computation of evolutionary distances// SIAM. J. Appl. Math. (1974), vol. 26, №4, p. 787 793.

57. Sellers P.H. Pattern recognition in genetic sequences// Proc. Natl. Acal. Sci. USA (1979), vol. 76, №7, p. 3041.

58. Sankoff D., Gedergren R.J. Simultaneous comparison of three or more sequences related by a tree // Strings and macromolecules: The Theory and practice of sequence comparison. Reading, MA, Addison Wesley, (1983), p. 253-263.

59. Steele J. M. Long common subsequences and the proximity of two random strings// SIAM J. Appl. Math. (1982), vol. 10, №1, p. 731 737.

60. Shannon, Robert E., System Simulation: The Art and Science, Prentice-Hall, 1975.

61. Schlesinger, S., "Terminology for Model Credibility", Simulation, 32(3), 1979, pp. 103-104.

62. Takens F. Detecting Strange Attractors in Fluid Turbulence // Dynamical System and Turbulence, Springer Lecture Notes in Mathematics 898, Berlin, p. 366,1981

63. Trifonov E.N., Brendel V. GNOMIC: a dictionary of the genetic code// Philadelphia: Balaban Publishing., 1986, 272 p.

64. Thesen, Arne and Laurel E. Travis, Simulation For Decision Making, West Publishing Company, 1992.

65. Ukkonen E. An approximate string matching// Lect. Notes in Comput. Sci. (1983), №158, p. 487 495.

66. Weiner P. Lenear pattern matching algorithms// Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory (1973), p. 1 -11.

67. Waterman M.S. General methods of sequence comparison// Bull. Math. Biol. (1984), Vol. 46, p. 474 500.

68. Waterman M.S., Perlwits M.D. Line geometries for sequence comparison// Bull. Math. Biol. (1984), vol. 46, p. 576 577.

69. Waterman M.S., Smith Т.Е., Beyer W.A. Some biological sequence ma-trics// Advances in mathematics (1976), №20, p. 367 387.

70. Wong C.K., Chandra A.K. Bound for the string correction problem// J. ASM. (1976), vol. 23, №1, p. 13 16.

71. Wagner B.M., Fisher M.J. The string to - string correction problem// J. ASM. (1974), vol. 21, №1, p. 168 - 173.

72. Zharkikh A.A., Rzhetsky Yu. I. Quick assessment of similarity of two sequences by comparison of their 1 — tuple frequencies//Biosystems, (1993), vol. 30, p. 93-111.

73. Александров А.А., Александров H.H., Бородовский М.Ю. и др. М.: Наука, 1990. 267 с.

74. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов/ — М.: Мир, 1979.

75. Айзенберг JI.A. Фомулы Карлемана в комплексном анализе. Перые приложения. Новосибирск: Наука, 1990. 248 с.

76. Бахмутова И.В., Гусев В.Д., Зарипов Р.Х., Титкова Т.Н. Выявление и анализ сходных фрагментов в музыкальных произведениях// В кн. Анализ символьных последовательностей (Вычислительные системы, вып. 113). Новосибирск, 1985, с. 3 - 45.

77. Бородовский М.Ю., Сприжицкий Ю.А., Голованов Е.И., Александров А.А. Статистические закономерности в первичных структурах функциональных областей генома Е. coli. 11. Неоднородные марковские модели// Молекуляр. Биология (1986), т. 20, с. 1024 1033.

78. Волькенштейн М.В. Энтропия и информация. М.: Наука, 1986. — с. 192

79. Гусев В.Д. Сложностные профили символьных последовательностей// В кн. Методы обработки символьных последовательностей и сигналов (Вычислительные системы, вып. 132). Новосибирск, 1989, с. 35-63.

80. Гусев В.Д. Характеристики символьных последовательностей// В кн. Проблемы обработки информации (Вычислительные системы, вып. 88). Новосибирск, 1981, с. 112 - 123.

81. Гусев В.Д., Куличков В.А., Титкова Т.Н. Анализ генетических текстов. 1.1- граммные характеристики// Эмпирическое предсказание и распознавание образов (Выч. системы, вып. 83). Новосибирск, Ин -т математики СО АН СССР. 1980. c.l 1 33.

82. Гусев В.Д. Механизмы обнаружения структурных закономерностей в символьных последовательностях// В кн. Проблемы обработки информации (Вычислительные системы, вып. 100). Новосибирск, 1983, с. 47-66.

83. Галягин Д.К., Фрик П.Г. Адаптивные вейвлеты (алгоритм спектрального анализа сигналов)

84. Гросберг А.Ю., Рабин И., Хавлин Ш., Нир А. Самоподобие в структуре ДНК: зачем нужны интроны? // Биофизика (1993), т. 38, 1, с. 75 -83.

85. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация, М.: Мир, 1985.-509с.

86. Горбань А.Н., Миркес Е.М., Свитин А.П. Полуэмпирический метод классификации атомов и интерполяции их свойств // Математическое моделирование в биологии и химии. Новые подходы. Новосибирск: Наука. Сиб. отделение, 1992.-е. 204-220.

87. Горбань А.Н. Обход равновесия Новосибирск: Наука, 1984. 236 с.

88. Горбань А.Н., Миркес Е.М., Свитин А.П. Метод мультиплетных покрытий и его использование для предсказания свойств атомов и молекул // Журнал физической химии.-1992.-Е.66, №6. с. 1503 -1510.

89. Горбань А.Н., Россиев A.A., Wunsch 2 D.C. Самоорганизующиеся кривые и нейросетевое моделирование данных с пробелами // сб. Нейроинформатика 2000, научная сессия МИФИ, 4.1, М., с. 40-45, 2000.

90. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. Новосибириск: Наука, 1996. 256 с.

91. Горбань А.Н., Попова Т.Г., Садовский М.Г. Классификация нуклео-тидных последовательностей по частотным словарям обнаруживаетсвязь между их структурой и таксономическим положением организмов// ЖОБ. 2003. Т. 64, №1. С. 51 63.

92. Горбань А.Н. Проблема скрытых параметров и задачи транспонированной регрессии // V Всеросс. семинар "Нейроинформатика и ее приложения": Тез.докл-Красноярск, 1997.-С. 15-16.

93. Горбань А.Н., Миркес Е.М., Попова Т.Г., Садовский М.Г. «Новый подход к изучению статистических свойств генетических последовательностей»/ Биофизика (1993), т. 38, вып. 5.-е. 762 767.

94. Горбань А.Н., Миркес Е.М., Попова Т.Г., Садовский М.Г. «Сравнительная избыточность генов некоторых организмов и вирусов»/ Генетика (1993), т. 29, № 11, с. 1413 1419.

95. Горбань А.Н., Попова Т.Г., Садовский М.Г. Избыточность генетических последовательностей и мозаичная структура генома//Мол. биол. (1994), т.28, вып. 2. с. 313 -324.

96. Георгиев Г.П. Гены высших организмов и их экспрессия. М.: Наука, 1989.-255 с.

97. Горбунова Е.О. Формально-кинетическая модель бесструктурного мелкозернистого параллелизма // Сиб. журн. вычисл. математики1999. Т.2, № з. С.239-256.

98. Гантмахер Ф.Р., Теория матриц, «Наука», 1967.

99. Ильин В.А., Позняк Э.Г. Линейная алгебра М: наука, физматлит, 1999.

100. Ефимов Н.В., Высшая геометрия, Физматгиз, 1961.

101. Зубков A.M., Михайлов В.Г., Предельные распределения случайных величин, связанных с длинными повторениями в последовательности независимых испытаний// Теория вероятностей и ее применение (1974), т. XIX, №1, с. 173 181.

102. Загоруйко Н.Г. Методы распознавания и их применение. Изд. Сов. Радио, М., 1972.

103. Загоруйко Н.Г., Елкина В.Н. Блок анализа данных в экспертной системе ЭКСНА. //Экспертные системы и анализ данных. Новосибирск, 1991, - Вычислительные системы: Вып. 144 - с. 57 - 175.

104. Загоруйко Н.Г., ЁлкинаВ.Н., Тимеркаев B.C. Алгоритм заполнения пропусков в эмпирических таблицах (алгоритм "ZET") // Вычислительные системы. Новосибирск, 1975. - Вып. 61. Эмпирическое предсказание и распознавание образов. - С. 3-27.

105. Злоба Е., Яцкив И. Статистические методы восстановления пропущенных данных. // Компьютерные модели и новые технологии-2002.- Т. 6, №.1.-С. 51-61.

106. Капитонов В.В., Титов И.И. Порядок расположения интронов и дальние корреляции в нуклеотидных последовательностях// ДАН (1994), т. 337, №6. с. 810 812.

107. Королев С.В., Соловьев В.В., Туманян В.Г. Новый метод поиска функциональных участков ДНК с использованием фрактального представления нуклеотидных текстов// Биофизика (1992), т. 37, вып. 5, с. 837-847.

108. Кирдин А.Н. Идеальная ансамблевая модель параллельных вычислений // Нейроинформатика и ее приложения. Тезисы докладов V Всеросс. семинара. Красноярск, КГТУ, 1997. С. 101.

109. Курош А.Г., Курс высшей алгебры, «Наука», 1970.

110. Колчанов Н.А., Соловьев В.В. Построение филогенетических деревьев по корреляциям в нуклеотидных последовательностях// ИНТ сер. Моле. биол. т. 21. М.: ВИНИТИ, 1985. 80 122.

111. Литтл Р.Дж.А., Рубин Д.Б. Статистический анализ данных с пропусками-М.: Финансы и статистика, 1991.

112. Ленг С., Алгебра, «Мир», 1968.

113. Левенштейн В.И. двоичные коды с исправлением выпадений, вставок и замещений символов// ДАН СССР. (1965), т. 163, №4, с. 845 -848.

114. Д.С. Лебедев, В.А. Гармаш. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958, №1 с. 68-69

115. Неменчинская Е.О., Кондратенко Ю.В., Садовский М.Г. Предварительные результаты в проблеме восстановления утерянных данных с помощью кинетической машины Кирдина // Вычислительные технологии.- 2004.- Т.9, № 1.- С.42 57.

116. Немытикова Л.А. Методы сравнения символьных последовательностей// В кн. Методы обработки символьных последовательностей и сигналов (Вычислительные системы, вып. 132). Новосибирск, 1989, с. 3-34.

117. Пасеков В.П. Генетические расстояния // Итоги науки и техники, сер. Общая генетика, т. 8 М.: ВИНИТИ, 1981. с. 3 - 75.

118. Попова Т.Г., Садовский М.Г. Точная мера избыточности генетических текстов / Экоген, вып. 2, изд во ТГУ, 1992, с. 9.

119. Россиев А.А. Моделирование данных при помощи кривых для восстановления пробелов в таблицах// Методы нейроинформатики, Сб. науч. Трудов, с 6-22, Красноярск, 1998.

120. Становление химии как науки. Всеобщая история химии / Под ред. Ю.И. Соловьева. -М.: Наука, 1983.-464 с.

121. Свойства элементов. В 2 х частях. Ч. 1. Физические свойства. Справочник. - М.: Метуллургия, 1976. - 600 с.

122. Садовский М.Г. Об информационной емкости символьных последовательностей. Выч. Технологии, 10 , № 4, 2005, 82 89.

123. Садовский М.Г. О сравнении символьных последовательностей. Выч. Технологии, 10, № 3, 2005, 108 116.

124. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. «Оптимизация технических систем» Учебное пособие. Красноярск: СИБУП, 1996

125. Соловьев В.В., Колчанов Н.А. Компьютерный анализ статистических характеристик нуклеотидных последовательностей // ИНТ сер. Молек. Биол. т. 21. М.: ВИНИТИ, 1985. с. 38 80.

126. Стратонович P.JI. Теория информации. М.: «Советское радио». -1975.

127. Физико химические свойства элементов. - Киев: Наукова думка. 1965-808 с.

128. Фоменко А.Т. Методика распознавания дубликатов и некоторые приложения// ДАН СССР (1981), т. 258, №6, с. 1326 1330.

129. Цымбал В.П. Теория информации и кодирование. К.: Высшая Шлола, 1977 г. - с. 288

130. Чупахина О.М. Сложностный анализ генетических текстов/ Авто-реф. .канд. Техн. Наук, Новосибирск, НИОХ, 1993, 18 с.

131. Шеннон К. Работы по теории информации и кибернетике. М. : Изд. иностр. лит., 1963. с.830

132. Эфрон Б. (1988) Нетрадиционные методы многомерного статистического анализа. Финансы и статистика, Москва.

133. Яблонский Г.С., Быков В.И., Горбань А.Н. Кинетические модели каталитических реакций. — Новосибирск: Наука, 1983. 253 с.

134. Яблоков А.В., Юсуфов А.Г. Эволюционное учение/ М.: Высшая школа, 1989. 335 с.142. http://www.ebi.ac.uk/genomes143. http://www.un.org

135. Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. Восстановление отсутствующих данных в символьных последовательностях. // Компьютерное моделирование и интеллектуальные системы: Сборник научных трудов. Запорожье: ЗНТУ, 2007. -206-212.

136. Сенашова М.Ю., Садовский М.Г., Рубцов А.Г. Кинетическая машина Кирдина в проблеме восстановления отсутствующих фрагментов символьных последовательностей. // Ползуновский альманах. Барнаул, 2006. №4. С. 59-63.

137. Рубцов А.Г., Садовский М.Г., Сенашова М.Ю. Восстановление отсутствующих данных и принцип максимального подобия // Вычислительные технологии / Издательство СО РАН. Новосибирск. 2008. Т. 13., 3, С. 114-127.

138. Сенашова М.Ю., Рубцов А.Г., Садовский М.Г. Кинетическая машина Кирдина и задача восстановления утерянных данных // "Радюелектрошка, 1нформатика, Управлшня". 2007. - № 1.-е. 87-93.

139. Сенашова М.Ю., Рубцов А.Г. Применение генетических алгоритмов для восстановления отсутствующих данных в символьных последовательностях. // Ползуновский альманах. Барнаул, 2007. №3. С. 84-87.

140. Сенашова М.Ю., Рубцов А.Г. Матричное представление частотного словаря в задаче восстановления отсутствующих данных. Матерлалы V Всесибирского конгресса женщин-математиков, 15-18 января 2008 г. Красноярск: РИО СФУ, 2008, -с. 367-372

141. Рубцов А.Г., Сенашова М.Ю. Матричное представление частотного словаря для восстановления отсутствующих данных // Журнал Сибирского федерального университета. Красноярск, серия «Математика и физика», январь 2009, том 2. №1. с. 105-115.