автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование и исследование механизмов структурообразования дискретных динамических систем

Введение

1. Обзор литературы

1.1 Что такое структура

1.2 Процессы структурообразования в сложных природных системах

1.2.1 Фракталы

1.2.2 Диссипативные структуры

1.2.3 Морфогенез

1.2.4 Структура ДНК

1.2.5 Третичная структура белка

1.3 Структурообразование, критические явления и самоорганизующаяся критичность

1.4 Структурообразование и задачи протекания

1.5 Математическое моделирование в исследованиях процессов структурообразования

1.6 Модели клеточных автоматов и их применения

2 Выявление связи структуры и динамики системы в моделях Булевых сетей

2.1 Введение

2.2 Определение Булевой сети

2.3 Характеристики динамики Булевых сетей, расстояние Гамминга

2.4 Структура взаимодействий и правила динамики

2.5 Результаты

2.6 Выводы

3 Моделирование простейших механизмов структурообра-зования

3.1 Введение

3.2 Формулировка модели

3.3 Результаты

3.4 Выводы

4. Исследование структур определяющих динамику сложных систем на примере сравнительного анализа структуры бактериальных геномов

4.1 Введение

4.2 Лингвистический анализ

4.3 Наиболее часто и наиболее редко встречающиеся последовательности

4.4 Сложность. Энтропия и информация

4.5 Анализ автокорреляций

4.6 Выводы Литература Приложения

1. Выявление связи структуры и динамики системы в моделях Булевых сетей

2. Моделирование простейших механизмов структурообра-зования

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

Наш век по праву можно назвать веком исканий в изобразительном искусстве, музыке, литературе и науке. Мы все еще не в состоянии предсказать, чем завершится эта

глава истории человечества. Несомненно лишь одно: она положила новый диалог между природой и человеком.

Пригожин И. "От существующего к возникающему"

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

Заметный интерес к этим проблемам существовал уже в начале второй половины прошлого столетия, когда преприни-мались попытки описания возникновения в макроскопических системах когерентных структур на основе общих физических принципов. Классическая термодинамика, как и другие теории "среднего поля", оказались малоэфективными для выяснения причин спонтанного образования порядка из беспорядка за счет большей хаотизации окружающей среды [1].

Согласно результатам статистики, - писали Л.Д. Ландау и Е.М. Лифшиц, - обсуждая 2-е начало термодинамики, - вселенная должна была бы находиться в состоянии полного статистического равновесия. Между тем ежедневный опыт убеждает нас в том, что свойства природы не имеют ничего общего со свойствами равновесной системы, а астрономические данные показывают, что то же самое относится и ко всей доступной нашему наблюдению колоссальной области Вселенной [2].

Предлагаемая работа состоит из введения, обзора литературы и трех основных частей:

1) Булевы сети в исследованиях связи структуры и динамики системы;

2) Выявление простейших механизмов структурообразова-ния;

3) Сравнительный анализ структуры бактериальных геномов.

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

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

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

1 Обзор литературы

1.1 Что такое структура

Понятие структуры часто употребляется, однако, далеко не всегда оно определяется однозначно. С другой стороны, трудно переоценить его важность для современной науки. Нет ни одной отрасли знания, где в той или иной форме не использовалось бы представление о структуре [3].

Одно из наиболее удачных определений структуры дал Кре-бер: "Каждая система состоит из элементов, упорядоченых определенным образом и связаных определенными отношениями. Под структурой системы мы понимаем способ организации элементов и характер связи между ними. При этом не существенно, какова природа элементов. Говоря о структуре системы, мы не обращаем внимания на то, какие элементы ее составляют, а рассматриваем лишь совокупность отношений между ними. Структура системы, определяемая как совокупность отношений, задает связь между элементами системы. "В большом энциклопедическом словаре можно найти такое определение структуры: "Структура - совокупность устойчивых связей объекта, обеспечивающих его целостность и тождественность самому себе, т.е. сохранение основных свойств при различных внутренних и внешних изменениях" [4].

В реальных системах различают пространственные и временные структуры. Структуры пространственного типа изучаются с древних времен. Демокрит учил: "все состоит из невидимых для нас крошечных частичек, настолько малых, что меньше и представить не возможно". Эти частички он назвал атомами, что значит - неделимые.

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

В 1897 году дробление материи опустилось ниже атомных размеров. Сразу возник вопрос о структуре атома. Одна из первых моделей атома, предложенная в 1903 году Д. Томсо-ном, представляла собой заряженую сферу с вкрапленными в нее незначительными по размеру, в сравнении с атомом, электронами. Практически в то же время Ж. Перреном была выдвинута гипотеза о планетарной модели атома. Впоследствие подтвержденная опытами Э. Резерфорда.

Издревне люди, глядя на ночное небо, выделяли на нем звездные скопления, ассоциировавшиеся с животными, богами и предметами. Так появились известные ныне созвездия. Более детальные астрономические наблюдения обнаружили, что окружающая нас Вселенная далеко как не однородна, так выделялись галактики и системы.

Появление пространственного порядка и передача информации в системе, изначально однородной, является центральной проблемой эмбриогенеза.

Временные структуры неотделимы от динамики системы, законов движения, здесь особенно важны принципы однонаправленности времени и причинности.

4.6 Выводы

На основе проведенных статистических исследований ДНК текстов можно сделать следующие выводы.

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

Выявлена связь между индексом распределения частоты встречаемости слов (а) и энтропией: чем меньше а, тем больше энтропия.

Результаты полученные в исследовании наиболее редких слов указывают на существенно неслучайный характер ДНК текстов и позволяют обнаружить биологически значимые единицы, как, например, сайты рестрикции. Что свидетельствует о важности подобных исследований.

Характеристики не зависят от размеров геномов.

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

Автокорреляции на малых масштабах присутствуют в рассмотрении коротких (п = 3) слов и практически отсутствуют для длинных.

Особенно интересный результат анализа автокорреляций получен для тЫЪ генома. В данном случае корреляции с период 3 осцилляцими существенны даже на очень больших масштабах, причем для любой, из рассмотренных, длины слова.

Следует также отметить нетипичные (отличные от остальных) характеристики tpal генома: наименьший индекс а, автокорреляции на масштабах 2 и 4, тот факт, что доминирующее слово состоит из CG повторов (что является редчайшей комбинацией в других геномах), наличие всех возможных слов вплоть до 7 уровня, максимум энтропии. Совокупность этих факторов позволяет утверждать, что этот геном является самым бесструктурным из исследованных.

В целом статистический анализ показывает, что даже бактериальные геномы сильно различаются между собой. Не были обнаружены какие-либо сходства в геномах, принадлежащих одному классу (например, Pyrococcus: pabyssi, pyro; Chla-mmydia: cpneu, ctra; Mycoplasma: mpneu, mgen).

He следует утверждать, что возможна разработка какой-либо общей схемы клфссификации геномов по статистическим характеристикам. Всегда существуют исключения. Так например, слова с CG повторами могут встречаться как среди наиболее, так и среди наименее употребимых. CG фрагменты в доминирующих словах чаще бывают в более длиных геномах (ecoli, mtub, synecho), в то же время, геном bsub длиннее synecho, но не содержит таких фрагментов. Резонные заключения можно делать только на основе как можно большего набора факторов. Так можно предположить, что отсутствие слов на б уровне в hpyl и mjan геномах (имеющих среднюю длину среди исследованых) связано с малым значением энтропии и присутствием корреляций для слов длины 7 более чем на одном масштабе. Очень сильные корреляции тЫЬ генома можно связать с довольно малой энтропией (этот геном яляется пятым среди исследованных, расположеных в порядке возрастания энтропии) тогда, как более длинные геномы есоИ, ЬвиЬ, Бупеско занимают 17, 18, 19 соответственно позиции в этом ряду. Подобные факторы могут указывать на наличие у этого генома специфической структуры.

1. Пригожин И. "Введение в термодинамику необратимых процессов", Изд-во Иностр. Лит., Москва (I960)

2. Л.Д. Ландау, Е.М. Лифшиц "Статистическая физика", Наука, Москва (1964);

3. Эбелинг В. "Образование структур при необратимых процессах", Мир, Москва (1979)4. "Большой Энциклопедический Словарь "под ред. A.M. Прохорова т. 2, Советская Энциклопедия, Москва (1991) с. 422

4. Белоусов Б.П. "Рефераты по радиационной медицине за 1958", Медгиз, Москва (1959), с. 145

5. Жаботинский A.M. Биофизика т. 9 (1964) с. 306

6. Жаботинский A.M. "Концентрационные автоколебания" Наука, Москва (1974)

7. В. Mandelbrot "The fractal geometry of nature", Freeman, New York (1983)

8. B. Mandelbrot "Possible refinement of the lognormal hypothesis concerning the distribution of energy dissipation in intermittent turbulence. In: Statistical Modelsand Turbulence "Lecture Notes in Physics 12 Springer, Amsterdam, 333 (1972)

9. B. Mandelbrot "Intermittent turbulence in self-similar cascades: Divergence of high moments and dimansion of the carrier "J. Fluid Mech. 62 331 (1974)

10. Frisch U., Parisi G. "On the singularity structure of fully developed turbulence.-In Turbulence and Predictability in Geophysical Fluid Dynamics and Climate Dynamics"North-Holland, New York, p.84 (1985)

11. Benzi R., Paladin G., Parisi G., Vulpani A. "On the multifractal nature of fully developed turbulence and chaotic systems", J. Phys. A 17 35211984)

12. Grassberger P. "Generalized dimentions of strange attractors"Phys. Lett. A 97, 227 (1983)

13. Hentschel H.G.E., Procaccia I. "The infinite number of generalized dimensions of fractals and strange attractors"Physica 8, 435 (1983)

14. Feigenbaum M.J., Jensen M.N., Procaccia I. "Time ordering and the thermodynamics of strange sets: Theory and experimental tests"Phys. Rev. Lett. 57, 1503 (1986)

15. Katzen D., Procaccia I. "Phase transitions in the thermodynamic formalism of multifractals'Thys. Rev. Lett. 58, 1169 (1987)

16. Meakin P., "Scaling properties for the growth probability measure and harmonic measure of fractal structures "Phys. Rev. A 35, 2234 (1987)

17. Rammal R., Tannous C., Breton P., Tremblay A.M.S. "Flicker (1/f) noise in percolation networks: A new hierarchy of exponents "Phys. Rev. Lett. 54, 1718 (1985)

18. Aharony A. "Percolation. In: Directions in Condenced Matter Physics"World Scientific, Singapore p.l (1986)

19. Blumenfeld R., Meir Y., Aharony A., Harris А.В., "Resistance fluctuations in randomly diluted networks"Phys. Rev. В 35, 3524 (1987)

20. Гленсдорф П., Пригожин И. "Термодинамическая теория структуры, устойчивости и флуктуаций", Мир, Москва (1973)

21. Уоддингтон К. "Морфогенез и генетика", Мир, Москва (1964)

22. А.А. Алексалдров, Н.Н. Александров, М.Ю. Бородов-ский и др. "Компьютерный анализ генетических текстов", Наука, Москва (1990)

23. Е.М. Попов "Проблема белка"2 Наука, Москва (1996)

24. Gutenberg В., Richter С. Е., "Seismicity of the Earth", Princeton Univ. Press, Princeton (1949)

25. Bak P., Chen K., "Fractal Dynamics of Earthquakes "in Barton С. C. and Lapointe P.R., eds. "Fractals in the Earth Sciences", Plenum, New York (1994)

26. Chen K., Bak P. "Scale Dependent Dimension in the Forest Fire Model", preprint in cond-mat/9912417

27. Bak P., Sneppen K., "Punctuated Equilibrium and Criticality in a Simple Model of Evolution"Phys. Rev. Lett. 71, 4083 (1993)

28. Paczuski M., Maslov S., and Bak P., "Field Theory for a Model of Self-Organized Criticality"Europhys. Lett. 27, 97 (1994)

29. Mardanov K. A., Pismak Yu. M., "Two models of biological evolution on the basis of Bak-Sneppen approach"J. Tech. Phys. 38, 301 (1997)

30. Yu. M. Pismak, "Bak-Sneppen model forself-orginized biological evolution exact results and possible modifications"J. Tech. Phys. 38, 327 (1997)

31. O.V. Kovalev, Yu. M. Pis'mak and V. V. Vechernin, "Self-orginized criticality in the model of biological evolutiondescribing interaction of 'coenophilous' and 'coenophobous' species"Europhys. Lett. 40(4), 471 (1997)

32. K. Nagel, M. Pachuzski, "Emergent Traffic Jams"Phys. Rev. E 51, 2909 (1995)

33. Y. Shi "Self-organization in BML Traffic Flow Model: Analytical Approaches"Commun. Theor. Phys. 31, 85 (1999)

34. Bak P, Tang C., Wiesenfeld K., "Self-orginized criticality"Phys. Rev. A 38, 364 (1988)

35. Raup, M. D., "Biological Extinction in Earth History"Science 231, 1528 (1986)

36. Gould, S. J. and Eldrege, N., "Punctuated Equilibrium: The Tempo and Mode of Evolution Reconsidered"Paleobiology 3 114 (1977)

37. A.JI. Эфрос "Физика и геометрия беспорядка", Квант, Москва (1982)

38. Яглом И. М. "Математические структуры и математическое моделирование", Сов. радио, Москва (1980)

39. Дж. Эндрюс, Р. Мак-Лоун "Мат. моделирование", Мир, Москва (1979)41. von Neumann J., "The general and logical theory of authomata"in J. von Neumann Collected Works 5, 288 (1963)

40. Thom R. "A Global Dynamical Scheme for Vortebrate Embryology"Som. Mat. Questions in Biology, Amer. Mat. Soc, 3 (1973)

41. Greenberg J.M., Hassard B.D., Hastings S. P.,"Pattern formation and periodic structures in systems modelled by reaction-diffusion equations", Bull. Am. Math. Soc. 84,1296 (1978)

42. Gerola H., Seiden P.,"Stochastic star formation and spiral structure of galaxies", Astrophys. J. 233, 129 (1978)

43. Baer R. M., Martinez H. M., "Automata and biology"Ann. Rev. Biophys. 3, 255 (1974)

44. Herman G. T., "Computing ability of a developmental model for filamentous organisms", J. Theor. Biol. 25, 421 (1969)

45. Kitagawa T., "Cell space approaches in biomathematics", Math. Biosci. 19, 27 (1974)

46. Stivens P. S., "Patterns in Nature", Little and Brown, Boston (1974)

47. Thompson D'A. W., "On growth and form", abridged ed. edited by J. T. Bonner, Cambridge University, Cambridge (1961)

48. ApSimon H.G., "Periodic forests whose largest clearings are of size 3", Philos. Trans. R. Soc. London, Ser. A 266, 113 (1970)

49. ApSimon H.G., "Periodic forests whose largest clearings are of size n'4", Proc. R. Soc. London, Ser. A 319, 399 (1970)

50. Miller J. C. P., "Periodic forests of stunted trees", Philos. Trans. R. Soc. London, Ser. A 266, 63 (1970)

51. Miller J. C. P., "Periodic forests of stunted trees", Philos. Trans. R. Soc. London, Ser. A 293, 48 (1980)

52. Sutton C., "Forests and numbers and thinking backwards", New Sei. 90, 209 (1981)

53. Deutsch E.S., "Thinning algorithms on rectangular, hexagonal and triangular arrays", Commun. ACM 15, 827 (1972)

54. Rosenfeld A., "Picture Languages", Academic, New York (1979)

55. Sternberg S. R., "Language and architecture for parallel image processing"Pattern Recognition in Practice, edited by

56. E. S. Gelesma and L. N. Kanal North-Holland, Amsterdam, p.35 (1980)

57. Derrida B., Flyvbjerg H., "Multivalley structure in Kauffman's model: analogy with spin glasses"J. of Phys. A 19 L1003 (1986)

58. Derrida B., Flyvbjerg H., "Distribution of local magnetisations in random networks of automata"J. of Phys. A 20 L1107 (1987)

59. Bornholdt S., Sneppen K., "Neutral Mutations and Punctuated Equilibrium in Evolving Genetic Networks"Phys. Rev. Lett. 81(1) 236 (1998)

60. Glass L., Hill C., Mestl T., "Nonlinear Dynamics of Gene Networks"Pacific Symposium of Biocomputing '98 (1998)62. de Sales J.A., Martins M.L., Stariolo D.A., "Cellular automata model for gene networks "Phys. Rev. E 55(3) 3262 (1997)

61. Thomas R., "Boolean Formalization of Genetic Control Circuits"! Theor. Biol. 42 563 (1973)

62. Sompolinsky H., Crisanti A., "Chaos in Random Neural Networks "Phys. Rev. Lett. 61(3) 259 (1988)

63. Mestl T., Bagley R.J., Glass L., "Common Chaos in Arbitrary Complex Feedback Networks"Phys. Rev. Lett. 79(4) 653 (1997)

64. Wolfram S., "Statistical mechanics of cellular automata"Rev. Mod. Phys. 55 601 (1983)

65. A. Turing Proc. London Math. Soc. 2(42), 230 (1936)

66. J. von Neumann "The general and logical theory of automata", coll. works, 5 McMillan, New York (1951)

67. J. von Neumann "Theory of self-reproducing automata", A.W.Burks (Ed.), University of Illinois Press, Illinois (1966)

68. Kauffman S.A., "Metabolic Stability and Epigenesis in Randomly Constructed Genetic Nets"J. Theor. Biol. 22 437 (1969)

69. Luque B., Sole R.V., "Controlling chaos in random Boolean networks"Europhys. Lett. 37(9) 597 (1997)

70. Derrida B., Pomeau Y., Europhys. Lett. 1(2) 45 (1986)

71. Derrida B., Stauffer D., "Phase Transitions in Two-Dimensional Kauffman Cellular Automata"Europhys. Lett. 2(10) 739 (1986)

72. Bastolla U., Parisi G., "Closing probabilities in the Kauffman model: an annealed computation"Physica D 98 1 (1996)

73. Kauffman S.A., "Requirements for evolvability in complex systems: orderly dynamics and frozen components "Physica D 42 135 (1990)

74. Bastolla U., Parisi G., "Relevant Elements, Magnetization and Dynamical Properties in Kauffman Networks: a Numerical Study"Physica D 115 203 (1998)

75. Bastolla U., Parisi G., "The Modular Structure of Kauffman Networks" Physica D 115 219 (1998)

76. K.Ho, A. Shvartsburg, B. Pan, Z. Lu, C. Wang, J. Wacker, J. Fye, M. Jarrold, Nature 392, 582 (1998);

77. A.Czirok, E.Ben-Jacob, I.Cohen, T.Vicsek, Phys. Rev. E 54, 1791 (1996).

78. T.Witten, L.M.Sander, Phys. Rev. Lett. 47, 1400 (1981);81. for reviews of DLA see P.Meakin, "Phase Transitions and Critical Phenomena", 12, eds. C. Domb and J.L. Lebowitz Academic, New York (1988)

79. S. Liang, S. Fuhrman, R. Somogy, Proc. Pacific Symposium on Biocomputing 1998, 18 (1998)

80. J. Reinitz, D.H. Sharp, Mech. of Development 49, 133 (1995)84 8586 8788