Алгоритмы компьютерного исследования случайных процессов и структур в естественных науках тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Покровская Ольга Дмитриевна

• Покровская Ольга Дмитриевна
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Покровская Ольга Дмитриевна

Введение

1 Оптимальный алгоритм случайного блуждания на плоскости для определения первого пересечения

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

1.2 Метод Монте-Карло

1.3 Модель ограниченной диффузии

1.4 Описание алгоритма случайного блуждания частицы на плоскости

1.5 Зависимость точности решения от количества частиц

1.6 Зависимость точности решения от размера шага

1.7 Новые алгоритмы

1.8 Выводы

2 Алгоритм генерации пенной структуры на плоскости и в пространстве

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

2.2 Алгоритм генерации пенной структуры

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

2.4 Особенности генерации случайного вектора в пространстве

2.5 Алгоритм генерации пенной структуры в пространстве

2.6 Выводы

3 Поиск естественного отбора в чилийской популяции по предсказанию локального происхождения геномов

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

3.2 Модель Райта-Фишера

3.3 Материалы и методы

3.4 Результаты

3.5 Выводы

Заключение

Литература

Приложение Свидетельство о государственной регистрации программы для ЭВМ

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

Введение

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

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

В первой задаче диссертации исследовались численные алгоритмы стохастического решения двумерного уравнения Лапласа с задачей определения точности оценки решения на границе. Исследование решения двумерного уравнения Лапласа как теоретически так и численно остаётся актуальной задачей. Такие исследования проводятся как в непрерывном пределе, например, исследование течений Хеле-Шоу [2], так и численно. Мы исследуем численно решения двумерного уравнения Лапласа, связанные со структурами роста. Для исследования математических свойств таких структур используется модель роста ограниченной диффузии - Diffusion Limited Aggregation (DLA) [15]. В этой модели главным элементом является диффузия, не учитываются такие факторы как, например, вязкость и поверхностное натяжение. В этом случае плотность вероятности диффундирующей частицы описывается уравнением Лапласа. Известно, что уравнение Лапласа со сложной границей можно решать методом случайного блуждания [3]. При этом ответ зависит от дискретизации пространства блуждания. Дискретизация подразумевает разбиение области регулярной

решеткой, что приводит к специфике, например, росту случайного агрегата. Модель ЭЬЛ была сформулирована на решётке, что накладывает ограничения на получаемые структуры, например, фрактальная размерность существенно зависит от симметрии решетки и для квадратной решетки она асимптотически стремится к 3/2, в то время как в непрерывном пределе ее фрактальная размерность равна 1.71 [7]. По сути, симметрия решетки влияет на геометрические и математические свойства решения. Представляет интерес исследование диффузии в пространстве без его разбиения на решётку. При этом возникает естественный вопрос о влиянии размера шага случайного блуждания частицы на точность оценки решения на границе области блуждания. Решению этой проблемы посвящена первая часть диссертации.

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

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

Вторая задача - это задача стохастической генерации пеноподобных структур. Эта задача может быть отнесена к области стохастической геометрии. Задача состоит в разработке алгоритма генерации пеноподобной случайной структуры, обладающей двумя отличительными свойствами - жесткостью и малой, по сравнению со сплошным телом, плотностью. Далее мы исследуем возможные магнитные свойства таких структур. В работе исследуются пеноподобные структуры при помощи компьютерного моделирования. Исследование пенопо-добных структур получило особое развитие в последнее время в связи с перспективой их использования в качестве контейнеров для хранения водорода [8] [39]. В частности, было выяснено что пенные структуры из платины и палладия являются наиболее перспективными для создания элементов хранения водорода.

Они обладают лучшими характеристиками полного цикла водородных элементов, как по удерживанию так и по отдаче водорода. Пеноподобные структуры из платины и палладия отличаются от других материалов наличием магнитных свойств. Природа магнетизма этих материалов является пока нераскрытой: сплошные образцы палладия и платины являются диамагнетиками или парамагнетиками [30], двумерные - ферромагнетиками [30-32]. В то же время выяснилось, что не существует простой модели магнитных систем на структурах со случайной геометрией, таких как пеноподобные структуры. Одна из задач диссертационного исследования состоит в разработке алгоритма генерации пеноподобных структур на плоскости и в пространстве, а также исследование модели Изинга на таких случайных структурах. Нами разработаны алгоритмы генерации пеноподобных структур на плоскости и в пространстве, и исследованы их статистические и геометрические свойства. Мы исследовали модель Изинга на плоской пеноподобной структуре и выяснили что низкотемпературное поведение магнитной восприимчивости в нашей модели качественно похоже на экспериментально обнаруженное низкотемпературное поведение магнитной восприимчивости в палладиевой пене.

Третья задача компьютерного моделирования, исследованная в диссертации, относится к области статистической геномики. В популяционной геномике в подавляющем большинстве случаев не представляется возможным верифицировать метод на экспериментальных данных в силу отсутствия известных значений оцениваемых параметров или изучаемых характеристик. Поэтому для проверки корректности работы разрабатываемых методов исследования, а также для верификации полученных научных результатов широко используется компьютерное моделирование. Существуют компьютерные симуляторы, например, шэрпше [1] для моделирования генеалогий и генетических данных в ко-алесцентной модели, симуляторы БЕЬЛМ [49] и БЫМ [50] для моделирования естественного отбора и эпистаза, симулятор УОэт [51] для моделирования вирусных генеалогий и другие. Отметим, что иногда одни и те же модели и алгоритмы отлично показывают себя в совершенно разных областях науки. Ярким примером являются компартментные модели [52] и алгоритм Гиллеспи [53], использующиеся для описания и численного моделирования в физической химии (химические реакции между молекулами газа) и в эпидемиологии (динамика эпидемии и эпидемиологические траектории). В нашем исследовании мы при-

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

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

Цель и задачи исследования

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

Задачами исследования являются:

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

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

3. Разработка численных алгоритмов генерации пеноподобных структур на плоскости и в трёхмерном пространстве.

4. Изучение магнитных свойств двумерной пеноподобной структуры.

5. Обнаружение признаков естественного отбора после примешивания в чилийской популяции.

Степень разработанности темы исследования

В первой главе диссертационного исследования изучается случайное блуждание частицы на плоскости. Одним из методов построения фракталов является выполнение специальной рекурсивной процедуры. В статье [15] был предложен алгоритм агрегации, ограниченной диффузией DLA (Diffusion Limited Aggregation). Основная идея алгоритма состоит в том, что рост кластера на квадратной решетке происходит в результате налипания случайно двигающихся частиц на растущую структуру. Алгоритм DLA применяется для разного рода задач. Это, например, изучение фотокатализаторов [16] и изучение роста речной сети [17].

В работе [19] был предложен алгоритм случайного блуждания частицы на плоскости с точным численным учетом граничного условия на бесконечности. В этом алгоритме частица при удалении на какое-то расстояние от растущего кластера не уничтожается, а с известной аналитически вероятностью возвращается на радиус рождения и продолжает блуждать. Вероятность возвращения на радиус рождения выводится из уравнения Лапласа, с использованием известной связи между вероятностью первого пересечения поглощающей окружности в процессе случайного блуждания и распределением электрического потенциала, описываемого уравнением Лапласа. В статье также была уточнена фрактальная размерность получившегося в ходе моделирования объекта. Уход от моделирования на решетке позволяет получить более точные результаты, но при этом время, затраченное частицей на блуждание и последующее прилипание, сильно растёт. В итоге, чтобы результаты были максимально приближены к аналитическим расчетам, частице требуется перемещаться с очень маленьким шагом, что сильно увеличивает время моделирования.

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

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

Не удалось обнаружить в научной литературе работы по компьютерному моделированию пеноподобных структур, а также исследований магнитных

свойств таких структур. Компьютерные исследования ограничены исследованием магнитных свойств одномерных атомных цепочек.

Третья глава посвящена поиску признаков естественного отбора в популяции чилийцев после колумбийского обмена. Обнаружение сигнала положительного естественного отбора (positive selection) в популяциях по всему миру помогает раскрыть эволюционную историю человека, а также генетическую основу разных заболеваний и иных фенотипических признаков [44]. Большинство эволюционных геномных исследований человека было проведено для европейского, африканского и азиатского населения. Однако население с коренным американским происхождением не было достаточно изучено [45]. Отчасти это связано с: 1) отсутствием общедоступных геномов нескольких популяций коренных американцев и их смешанных латиноамериканских потомков; 2) технической сложностью выявления генетических факторов, специфичных для происхождения, в смешанных популяциях с различными континентальными предками и сложной демографической историей. В отличие от перуанцев, колумбийцев, мексиканцев и пуэрториканцев, для которых имеется общедоступное секвенирование всего генома [46], для чилийцев таких данных нет.

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

Научная новизна диссертационного исследования заключается в разработке новых алгоритмов и изучении свойств ранее неизученных моделей. Помимо этого в диссертации исследуются новые данные генотипов чилийцев.

Более подробно научная новизна раскрывается в следующих пунктах:

1. Впервые предложен эффективный алгоритм с переменным размером шага для моделирования случайного блуждания частицы на плоскости и её прилипания к окружности фиксированного радиуса.

2. На основании проведенных численных расчетов впервые предложено аналитическое выражение для зависимости точности моделирования от шага частицы.

3. Впервые разработан алгоритм генерации двумерной и трёхмерной пенопо-добной структуры с типичными свойствами наблюдаемых экспериментально структур: низкой плотностью и механической жесткостью.

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

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

Основные результаты, выносимые на защиту:

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

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

3. Разработан алгоритм для генерации пеноподобных структур на плоскости и в пространстве. Проверено соответствие геометрических характеристик моделируемых структур с аналитическими расчётами.

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

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

Апробация результатов исследования

1. «Зависимость результатов моделирования процесса случайного блуждания от конечного шага», ежегодная межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов имени Е.В. Армен-ского, 19 февраля - 1 марта 2018г.

2. «Алгоритмы с переменным размером шага для моделирования процесса случайного блуждания на плоскости», ежегодная межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов имени Е.В. Арменского, 18 февраля - 28 февраля 2019г.

3. «Алгоритм генерации отрезков на плоскости для моделирования двумерной пены», ежегодная межвузовская научно-техническая конференция студентов, аспирантов и молодых специалистов имени Е.В. Арменского, 25 февраля - 4 марта 2020г.

4. «Method for foam generation in plane» на международной конференции International Conference on Computer Simulation in Physics and beyond, 12-16 октября 2020г.

5. «Моделирование магнитных свойств двумерной металлической пены» на международной конференции Суперкомпьютерные дни в России 27-28 сентября 2021г.

Свидетельство о государственной регистрации ПО:

• Свидетельство о государственной регистрации программы для ЭВМ №2018665832 «Случайное блуждание с переменным шагом и первое пересечение границы»(см. Приложение)

Публикации автора по теме диссертации

Все публикации входят в международную систему цитирования Scopus.

1. Klimenkova O., Menshutin A., Shchur L. Variable-step-length algorithms for a random walk: Hitting probability and computation performance // Computer Physics Communications. 2019. Vol. 241. P. 28-32.

2. Klimenkova O., Menshutin A., Shchur L. Influence of the random walk finite step on the first-passage probability // Journal of Physics: Conference Series. 2018. Vol. 955. No. 012009. P. 1-6.

3. Klimenkova O., Shchur L. Algorithm for foam generation in plane // Journal of Physics: Conference Series. 2021. Vol. 1740. No. 012030. P. 1-5.

4. Vicuña, L., Klimenkova, O., Norambuena, T., Martinez, F. I., Fernandez, M. I., Shchur, V., Eyheramendy, S., Postadmixture selection on Chileans targets haplotype involved in pigmentation, thermogenesis and immune defense against pathogens //Genome Biology and Evolution. - 2020 - 12(8) - p. 1459-1470.

Краткое содержание работы

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

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

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

В третьей главе исследуется популяция чилийцев Мапуче после колумбийского обмена. По геномам восстанавливается популяционная и эволюционная история чилийского населения. Выявлены признаки PAS (The Post-admixture Selection, отбор после примешивания) в наших данных в следующих участках генома. Самый сильный сигнал естественного отбора относится к сегменту ДНК, который участвует в термогенезе, а также отвечает за регуляцию количества пигментов меланина в волосяных фолликулах и в коже.

Глава 1

Оптимальный алгоритм случайного блуждания на плоскости для определения первого пересечения

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

Моделирование случайного блуждания и роста случайных структур является общим подходом для изучения явлений и процессов во многих областях науки и техники. В математике случайное блуждание можно использовать, например, для изучения задач о покрытии тора [4], в биологии - для изучения миграции лейкоцитов [5], в химии - для изучения формирования кристаллических узоров [6]. Процесс диффузии лежит в основе физической модели, которая приводит к образованию подобных структур. Часто описание эволюции системы через набор уравнений может быть невозможным, поэтому используются методы компьютерного моделирования основанные на рекуррентных процедурах.

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

Для моделирования случайного блуждания мы используем метод Монте-Карло и модель ограниченной диффузии (DLA - diffusion limited aggregation) [15].

Расчеты проводились на суперкомпьютерном кластере «Мантикоре» Научного центра РАН в Черноголовке (CPU: 2x Intel Xeon E5-2650v3, RAM: 64GB DDR4 2133 MHz). Все алгоритмы реализованы последовательно, на языке C++.

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

Этот и последующие разделы главы основаны на статьях [21] и [22].

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

1.2 Метод Монте-Карло

Особое место в физике и математике занимает стохастический метод Монте-Карло [9], [10].

Метод Монте-Карло был предложен в 1949 году в статье Метрополиса и Улама «Метод Монте-Карло» [11]. Суть метода можно объяснить так: вместо того, чтобы аналитически считать вероятность, можно просто провести большое количество испытаний и на основе результатов оценить вероятность события. Самый частый пример для демонстрации работы метода Монте-Карло это подсчет площади под графиком функции. Ограничим функцию прямоугольником, его площадь легко подсчитать. В прямоугольник будем набрасывать точки случайным образом (координаты по х и по у генерируются случайно). Посчитаем количество точек, попавших под кривую. Теперь, чтобы определить площадь криволинейной фигуры надо умножить площадь прямоугольника на часть частиц, попавших под кривую от всех сгенерированных частиц. Чем больше сгенерированных точек, тем точнее будет результат.

Метод Монте-Карло использует компьютерную генерацию псевдослучайных чисел. Существуют физические случайные генераторы, это, например, дробовой шум [12] - хаотичные флуктуации напряжений и токов относительно их среднего значения в цепях электрических и электронных устройств, но для численного моделирования физические генераторы слишком медленные и дорогие, поэтому используются компьютерные алгоритмы для генерации псевдослучайных чисел. Используя эти алгоритмы, нужно понимать, что никакой детерминированный алгоритм не сможет генерировать полностью случайные числа, но он позволяет генерировать числа, очень похожие по свойствам на случайные. В отличие от физических генераторов, где однажды полученную последовательность нельзя воспроизвести, в компьютерной генерации повторное воспроизведение возможно. Рано или поздно числа в последовательности начнут повторяться, это называется периодом генерации, и чем больше период, тем качественнее алгоритм. Другим требованием к генераторам является отсутствие корреляций. Для проверки этого требования используется набор стандартных тестов NIST (National Institute of Standards and Technology) [14].

Генераторы случайных чисел, работающие на компьютере, правильно называть генераторами псевдослучайных чисел, потому что числа, сгенерированные на компьютере, не в полной мере «случайны». В работе мы используем генератор Мерсенн Твистер с периодом 219937 [13].

1.3 Модель ограниченной диффузии

В 1981 году Виттен и Сандер изучали особенности строения веществ, таких как металлический пар, полученный в результате нагрева гальванической нити и последующего резкого охлаждения [15]. Особенность этой структуры в том, что мельчайшие частицы металла конденсируются на нити и в произвольном порядке слипаясь друг с другом, образуют кластеры, растущие в разные стороны. Авторы предложили модель, где на двумерной решетке, в начале координат помещается «затравочная» частица, в случайном месте на решетке появляется следующая частица, которая начинает совершать случайное блуждание, пока не «прилипнет» к «затравочной» частице. Вместе эти частицы образуют кластер. В дальнейшем новые частицы будут блуждать и прилипать к кластеру, таким образом он будет расти. Полученная в итоге структура и подвергается

изучению. В случае, если блуждая частица выйдет за границу решетки, она будет уничтожена и вместо неё генерируется новая частица. То, что частица, выходя за пределы решетки уничтожается, можно математически, в терминах уравнения Лапласа, записать так: потенциал на границе равен 1. В этой работе впервые предложена вышеописанная модель под названием DLA - diffusion limited aggregation, модель ограниченной диффузии. Пример такой структуры показан на Рис. 1.1

Рисунок 1.1: Пример роста случайной структуры с 50 млн частиц. Рисунок

предоставлен научным руководителем

Похожую модель в своей работе использовали Нимейер и его соавторы [18]. Они описывали явление - пробой в диэлектрике и изучали фрактальные свойства полученных на квадратной решетке объектов. В своей модели они использовали следующие правила:

• потенциал рассчитан в каждой точке решетки по формуле Лапласа с граничными условиями: на границе потенциал равен 1, на кластере равен 0;

Список литературы диссертационного исследования кандидат наук Покровская Ольга Дмитриевна, 2023 год

Литература

1. Kelleher, J., Etheridge, A.M. and McVean, G., Efficient coalescent simulation and genealogical analysis for large sample sizes //PLoS computational biology -2016 - 12(5), p.e1004842.

2. Lee, S.Y., Bettelheim, E. and Wiegmann, P., Bubble break-off in Hele-Shaw flows—singularities and integrable structures //Physica D: Nonlinear Phenomena - 2006 - 219(1) - pp.22-34.

3. Einstein, Albert. On the motion of small particles suspended in a stationary liquid //Ann. Phys - 1905 - 322(8) - p.549-560.

4. Grassberger P., How fast does a random walk cover a torus? //Physical Review E. - 2017 - 96(1) - p.012115.

5. Jones, P.J., Sim, A., Taylor, H.B., Bugeon, L., Dallman, M.J., Pereira, B., Stumpf, M.P. and Liepe, J., Inference of random walk models to describe leukocyte migration //Physical biology. - 2015 - 12(6) - p.066001.

6. Srivastava, R., Yadav, N. and Chattopadhyay, J., Growth and Form of Self-organized Branched Crystal Pattern in Nonlinear Chemical System //Springer Singapore - 2016.

7. Menshutin, A.Y. and Shchur, L.N., Morphological diagram of diffusion driven aggregate growth in plane: Competition of anisotropy and adhesion //Computer Physics Communications - 2011 - 182(9), pp.1819-1823.

8. Grochala, W. and Edwards, P.P. Thermal decomposition of the non-interstitial hydrides for the storage and production of hydrogen //Chemical reviews - 2004 - 104(3), pp.1283-1316.

9. Landau D., Binder K. A guide to Monte Carlo simulations in statistical physics. Cambridge university press - 2021

10. Sokal, A., Monte Carlo methods in statistical mechanics: foundations and new algorithms //Springer US. - 1997 - pp. 131-192

11. Metropolis N., Ulam S. The monte carlo method //Journal of the American statistical association. - 1949. - T. 44. - №. 247. - p. 335-341

12. Shen, Y., Tian, L. and Zou, H., Practical quantum random number generator based on measuring the shot noise of vacuum states //Physical Review A - 2010 - 81(6), p.063814.

13. Matsumoto M. and Nishimura T., Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. //ACM Transactions on Modeling and Computer Simulation (TOMACS). - 1998. - 8(1), pp.3-30.

14. Rukhin A., Soto J., Nechvatal J., Smid M. and Barker E., A statistical test suite for random and pseudorandom number generators for cryptographic applications. //Booz-allen and hamilton inc mclean va. - 2001

15. Witten Jr T. A., Sander L. M. Diffusion-limited aggregation, a kinetic critical phenomenon //Physical review letters. - 1981. - T. 47. - №. 19. - p. 1400.

16. Du, Y., Liu, M. and Guo, L., Scattering phase function of fractal aggregates of TiO2 particulate photocatalyst simulated with discrete dipole approximation //International Journal of Hydrogen Energy. - 2020 - 45(52), pp.28034-28043.

17. Wang, S., Ji, H., Li, P., Li, H. and Zhan, Y., Growth diffusion-limited aggregation for basin fractal river network evolution model //AIP Advances. - 2020 - 10(7), p.075317.

18. Niemeyer L., Pietronero L., Wiesmann H. J. Fractal dimension of dielectric breakdown //Physical Review Letters. - 1984. - T. 52. - №. 12. - p. 1033.

19. Menshutin A. Y., Shchur L. N. Test of multiscaling in a diffusion-limited-aggregation model using an off-lattice killing-free algorithm //Physical Review E. - 2006. - T. 73. - №. 1. - p. 011407.

20. Menshutin A. Y., Shchur L. N., Vinokur V. M.. Probing surface characteristics of diffusion-limited-aggregation clusters with particles of variable size. //Physical Review E. - 2007. - T. 75. - №. 1. - p. 010401.

21. Klimenkova O., Menshutin A., Shchur L. Influence of the random walk finite step on the first-passage probability //Journal of Physics: Conference Series. -IOP Publishing, 2018. - T. 955. - №. 1. - p. 012009.

22. Klimenkova O., Menshutin A., Shchur L., Variable-step-length algorithms for a random walk: hitting probability and computation performance //Computer Physics Communications - 2019. - 241, pp.28-32.

23. Menshutin A. Y., Scaling in the Diffusion Limited Aggregation Model //Physical review letters - 2012 - T. 108 - №. 1. - p. 015501

24. Antolini E., Palladium in fuel cell catalysis //Energy and Environmental Science.

- 2009 - 2(9) - pp. 915-931.

25. Pradhan D.K., Mishra A.K., Kumari S., Basu A., Somayazulu M., Gradauskaite E., Smith R.M., Gardner J., Turner P.W., N'Diaye A.T. and Holcomb M.B., Studies of Multiferroic palladium perovskites //Scientific reports. - 2019 - 9(1)

- p. 1685.

26. Miles R. E., Random polygons determined by random lines in a plane //Proceedings of the National Academy of Sciences of the United States of America. - 1964 - T. 52 - №. 4. - p. 901

27. Richards P. I., Averages for polygons formed by random lines //Proceedings of the National Academy of Sciences of the United States of America. - 1964. - T. 52. - №. 5. - C. 1160.

28. Goudsmit S., Random distribution of lines in a plane //Reviews of Modern Physics. - 1945 - T. 17 - №. 2-3. - p. 321

29. Miles R. E., The various aggregates of random polygons determined by random lines in a plane //Advances in Mathematics. - 1973 - T. 10 - №. 2. - p. 256-290

30. Zhu, M.J., Bylander, D.M. and Kleinman, L., Ferromagnetic properties of Pd monolayers //Physical Review B. - 1990 - 42(5), p.2874.

31. Sampedro, B., Crespo, P., Hernando, A., Litran, R., Lopez, J.S., Cartes, C.L., Fernandez, A., Ramirez, J., Calbet, J.G. and Vallet, M., Ferromagnetism in fcc

twinned 2.4 nm size Pd nanoparticles //Physical review letters. - 2003 - 91(23), p.237203.

32. Shinohara, T., Sato, T. and Taniyama, T., Surface ferromagnetism of Pd fine particles //Physical Review Letters. - 2003 - 91(19), p.197201.

33. Klimenkova O., Shchur L., Algorithm for foam generation in plane //Journal of Physics: Conference Series. - 2021 - Vol. 1740. No. 012030. p. 1-5.

34. Teng, X., Han, W.Q., Ku, W. and Hücker, M., Synthesis of ultrathin palladium and platinum nanowires and a study of their magnetic properties //Angewandte Chemie - 2008 - 120(11), pp.2085-2088.

35. Schottky, W. The rotation of atomic axes in solids (with magnetic, thermal and chemical applications) //Physikalische - 1922 - Z 23, pp. 448-55.

36. Klimenkova O., Моделирование магнитных свойств двумерной металлической пены. //Суперкомпьютерные дни в России. - 2021 - с. 116-123

37. Islam M.R. and Picu, R.C., Random fiber networks with inclusions: The mechanism of reinforcement. //Physical Review E. - 2019 - 99(6), p.063001.

38. Picu, R.C., 2011. Mechanics of random fiber networks—a review. //Soft Matter, 7(15), pp.6768-6785.

39. Gilbert, D.A., Burks, E.C., Ushakov, S.V., Abellan, P., et al. Tunable low density palladium nanowire foams. //Chemistry of Materials - 2017 - 29(22), pp.98149818.

40. Baxter R. J., Exactly solved models in statistical mechanics. //Elsevier - 2016

41. Wolff U., Collective Monte Carlo updating for spin systems. //Physical Review Letters - 1989 - 62(4), p.361.

42. Box G. E. P., Muller M. E. A note on the generation of random normal deviates //The annals of mathematical statistics. - 1958. - Т. 29. - №. 2. - p. 610-611.

43. Vicuña L., Klimenkova O., Norambuena T., Martinez F. I., Fernandez M. I., Shchur V., Eyheramendy S. Post-Admixture Selection on Chileans Targets Haplotype Involved in Pigmentation, Thermogenesis and Immune Defense

Against Pathogens // Genome Biology and Evolution. 2020. Vol. 12. No. 8. P. 1459-1470

44. Nielsen, R., Akey, J. M., Jakobsson, M., Pritchard, J. K., Tishkoff, S., Willerslev, E. Tracing the peopling of the world through genomics //Nature. - 2017. - T. 541. - №. 7637. - C. 302-310

45. Cheng JY, Racimo F, Nielsen R. 2019. Ohana: detecting selection in multiple populations by modelling ancestral admixture components. BioRxiv.

46. 1000 Genomes Project Consortium, A global reference for human genetic variation. //Nature. - 2015 - 526(7571), p.68-74.

47. Eyheramendy S, Martinez FI,Manevy F, Vial C, Repetto GM. Genetic structure characterization of Chileans reflects historical immigration patterns //Nature communications. - 2015 - 6(1) - p.6472.

48. Vicuna L, et al. 2019. Adaptation to extreme environments in an admixed human population from the Atacama Desert //Genome Biology and Evolution - 2019 -11(9) - pp.2468-2479.

49. Corbett-Detig, R., Jones, M. SELAM: simulation of epistasis and local adaptation during admixture with mate choice //Bioinformatics. - 2016 - 32(19), 3035-3037.

50. Messer, P.W., SLiM: simulating evolution with selection and linkage //Genetics - 2013 - 194(4), pp.1037-1039.

51. Shchur, V., Spirin, V., Sirotkin, D., Burovski, E., De Maio, N. and Corbett-Detig, R., VGsim: scalable viral genealogy simulator for global pandemic.//PLoS Computational Biology - 2022 - 18(8), p.e1010409.

52. Kermack, W.O. and McKendrick, A.G., A contribution to the mathematical theory of epidemics. //Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character - 1927 - 115(772), pp.700-721.

53. Gillespie, D.T. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions //Journal of computational physics -1976 - 22(4), pp.403-434.

54. Wright, S., 1937. The distribution of gene frequencies in populations. Proceedings of the National Academy of Sciences, 23(6), pp.307-320.

55. Durrett, R, Probability models for DNA sequence evolution (Vol. 2) //New York: Springer - 2008 - .

56. Bhatia, G., Tandon, A., Patterson, N., Aldrich, M. C., Ambrosone, C. B., Amos, C., ... Price, A. Genome-wide scan of 29,141 African Americans finds no evidence of directional selection since admixture //The American Journal of Human Genetics. - 2014. - T. 95. - №. 4. - C. 437-444.

57. Tataru P. et al. Statistical inference in the Wright-Fisher model using allele frequency data //Systematic biology. - 2017. - T. 66. - №. 1. - C. e30-e46.

58. Svedberg, J., Shchur, V., Reinman, S., Nielsen, R., Corbett-Detig, R. Inferring adaptive introgression using hidden Markov models //Molecular biology and evolution. - 2021. - T. 38. - №. 5. - C. 2152-2165.

59. Shchur, V., Svedberg, J., Medina, P., Corbett-Detig, R., Nielsen, R. On the distribution of tract lengths during adaptive introgression //G3: Genes, Genomes, Genetics. - 2020. - T. 10. - №. 10. - C. 3663-3673.

60. Cook N. D. Born to die: disease and New World conquest, 1492-1650. //Cambridge University Press - 1998 - T. 1.

Приложение Свидетельство о государственной регистрации программы для ЭВМ.

н

ж

ж

ж

ж

ж ж ж ж ж ж ж

ж

жжжжжж

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2018665832

Случайное блуждание с переменным шагом и первое пересечение границы

Правообладатель: Федеральное государственное бюджетное учреждение науки Научный центр Российской академии наук в Черноголовке (НЦЧ РАН) (№)

Автор: Клименкова Ольга Дмитриевна (К11)

Заявка № 2018663366

Дата поступления 26 Ноября 2018 Г.

Дата государственной регистрации

в Реестре программ для ЭВМ 11 декабря 2018 г.

Руководитель Федеральной службы по интеллектуальной собственности

Г. П. Ивлиев

Ж

ж ж

^ЖЖЖЖЖЖЖЖЖЖЖШШЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖЖ'