Модель НК

Модель NK — это математическая модель, описанная ее главным изобретателем Стюартом Кауфманом как «настраиваемый неровный» ландшафт приспособленности . «Настраиваемая неровность» отражает интуицию, что как общий размер ландшафта, так и количество его локальных «холмов и долин» можно регулировать посредством изменения двух его параметров, и , при этом длина цепочки эволюции и определение уровня неровности ландшафта. ${\displaystyle N}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\displaystyle K}$

Модель NK нашла применение в самых разных областях, включая теоретическое изучение эволюционной биологии , иммунологии , оптимизации , технологической эволюции , командной науки ^[1] и сложных систем . Модель также была принята в организационной теории , где она используется для описания способа, которым агент может искать ландшафт, манипулируя различными характеристиками самого себя. Например, агент может быть организацией , холмы и долины представляют прибыль (или ее изменения), а движение по ландшафту требует организационных решений (таких как добавление линеек продуктов или изменение организационной структуры), которые, как правило, взаимодействуют друг с другом и влияют на прибыль сложным образом. ^[2]

Ранняя версия модели, которая рассматривала только самые гладкие ( ) и самые неровные ( ) ландшафты, была представлена ​​в работе Кауфмана и Левина (1987). ^[3] Модель в том виде, в котором она известна в настоящее время, впервые появилась в работе Кауфмана и Вайнбергера (1989). ^[4] ${\displaystyle K=0}$ ${\displaystyle K=N-1}$

Одна из причин, по которой модель привлекла широкое внимание в оптимизации, заключается в том, что она является особенно простым примером так называемой NP-полной задачи ^[5] , что означает, что трудно найти глобальные оптимумы. Недавно было показано, что модель NK для K > 1 также является PLS-полной ^[6] , что означает, что, в общем, трудно найти даже локальные оптимумы приспособленности. Это имеет последствия для изучения открытой эволюции.

Типичный пример: приспособленность плазмиды

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

Для простоты мы моделируем плазмиду как кольцо из N возможных генов, всегда в одном и том же порядке, и каждый может иметь два возможных состояния (активный или неактивный, тип X или тип Y и т. д.). Затем плазмида моделируется двоичной строкой длиной N , и поэтому функция приспособленности равна . ${\displaystyle F:\{0,1\}^{N}\to \mathbb {R} }$

В простейшей модели гены не взаимодействуют друг с другом, и поэтому мы получаем , где каждый обозначает вклад в приспособленность гена в местоположении . $${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1})+f_{2}(S_{2})+\cdots +f_{N}(S_{N})}$$ ${\displaystyle f_{i}(S_{i})}$ ${\displaystyle S_{i}}$ ${\displaystyle i}$

Для моделирования эпистаза мы вводим еще один фактор K , количество других генов, с которыми взаимодействует ген. Разумно предположить, что на плазмиде два гена взаимодействуют, если они соседствуют, таким образом, например, когда K = 1 , а N = 5 , $${\displaystyle F(S_{1}S_{2}\cdots S_{N})=f_{1}(S_{1},S_{2})+f_{2}(S_{2},S_{3})+\cdots +f_{N-1}(S_{N-1},S_{N})+f_{N}(S_{N},S_{1})}$$

${\displaystyle F(00101)=f_{1}(0,0)+f_{2}(0,1)+f_{3}(1,0)+f_{4}(0,1)+f_{5}(1,0)}$

Модель NK обобщает это, допуская произвольные конечные K, N, а также допуская произвольное определение смежности генов (гены не обязательно лежат на окружности или отрезке прямой).

Математическое определение

Модель NK определяет комбинаторное фазовое пространство , состоящее из каждой строки (выбранной из заданного алфавита) длины . Для каждой строки в этом поисковом пространстве определяется скалярное значение (называемое пригодностью ). Если между строками определена метрика расстояния, то результирующая структура представляет собой ландшафт . ${\displaystyle N}$

Значения приспособленности определяются в соответствии с конкретным воплощением модели, но ключевой особенностью модели NK является то, что приспособленность данной строки представляет собой сумму вкладов каждого локуса в строке: ${\displaystyle S}$ ${\displaystyle f_{i}(S)}$

${\displaystyle F(S)=\sum _{i}{\tilde {f}}_{i}(S),}$

и вклад каждого локуса в целом зависит от его состояния и состояния других локусов: ${\displaystyle K}$

${\displaystyle {\tilde {f}}_{i}(S)=f_{i}(S_{i},S_{k_{i1}},\dots ,S_{k_{iK}}),}$

где - индекс -го соседа локуса . ${\displaystyle k_{ij}}$ ${\displaystyle j}$ ${\displaystyle i}$

Таким образом, функция приспособленности представляет собой отображение между строками длины K  + 1 и скалярами, которые в более поздней работе Вайнбергера называются «фитнес-вкладами». Такие фитнес-вклады часто выбираются случайным образом из некоторого заданного распределения вероятностей. ${\displaystyle f_{i}}$

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

Пример: модели спинового стекла

Одномерная модель Изинга спинового стекла обычно записывается как , где — гамильтониан, который можно рассматривать как энергию. $${\displaystyle H=-\sum _{i=1}^{N}J_{i,i+1}S_{i}S_{i+1}-\mu \sum _{i=1}^{N}h_{i}S_{i}}$$ ${\displaystyle H}$

Мы можем переформулировать это как частный случай модели NK с K=1 : определив В общем случае m-мерная модель Изинга на квадратной сетке является моделью NK с . $${\displaystyle H=F(S)=\sum _{i,j}f_{i,j}(S_{i},S_{j})}$$ $${\displaystyle f_{i}(S_{i},S_{i+1})=-J_{i,i+1}S_{i}S_{i+1}-\mu h_{i}S_{i}}$$ ${\displaystyle \{1,2,...,n\}^{m}}$ ${\displaystyle N=n^{m},K=m}$

Поскольку K приблизительно измеряет «жесткость» ландшафта приспособленности (см. ниже), мы видим, что с увеличением размерности модели Изинга ее жесткость также увеличивается.

Когда , это модель Эдвардса–Андерсона, которая точно решается. ${\displaystyle \mu =0}$

Модель Шеррингтона–Киркпатрика обобщает модель Изинга, позволяя взаимодействовать всем возможным парам спинов (вместо графа-сетки используйте полный граф ), таким образом, она также является моделью NK с . ${\displaystyle K=N-1}$

Разрешая взаимодействовать всем возможным подпоследовательностям спинов, а не просто парам, мы получаем модель с бесконечным диапазоном, которая также является моделью NK с . ${\displaystyle K=N-1}$

Настраиваемая топология

Иллюстрация настраиваемой топологии в модели NK. Узлы — это отдельные двоичные строки, ребра соединяют строки с расстоянием Хэмминга , равным единице. (слева) N = 5, K = 0. (в центре) N = 5, K = 1. (справа) N = 5, K = 2. Цвет узла обозначает его приспособленность, причем более красные значения имеют более высокую приспособленность. Вложение гиперкуба выбирается таким образом, чтобы максимум приспособленности находился в центре. Обратите внимание, что ландшафт при K = 0 выглядит более гладким, чем в случаях с более высокими значениями K.

Значение K контролирует степень эпистаза в модели NK или то, насколько другие локусы влияют на вклад приспособленности данного локуса. При K = 0 приспособленность данной строки является простой суммой индивидуальных вкладов локусов: для нетривиальных функций приспособленности глобальный оптимум присутствует и его легко найти (геном всех нулей, если f (0) > f (1), или всех единиц, если f (1) > f (0)). Для ненулевого K приспособленность строки является суммой приспособленностей подстрок, которые могут взаимодействовать, чтобы нарушить работу системы (рассмотрите, как достичь оптимальной приспособленности в примере выше). Таким образом, увеличение K увеличивает неровность ландшафта приспособленности.

Варианты с нейтральными пространствами

Голая модель NK не поддерживает явление нейтрального пространства — то есть наборы геномов, связанных одиночными мутациями, которые имеют одинаковое значение приспособленности. Было предложено две адаптации для включения этой биологически важной структуры . Модель NKP вводит параметр : доля вкладов приспособленности устанавливается равной нулю, так что вклады нескольких генетических мотивов вырождены ^{[ требуется ссылка ]} . Модель NKQ вводит параметр и обеспечивает дискретизацию возможных значений вкладов приспособленности, так что каждый вклад принимает одно из возможных значений, снова вводя вырождение во вклады некоторых генетических мотивов ^{[ требуется ссылка ]} . Голая модель NK соответствует случаям и при этих параметризациях. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle 2^{K}}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle P=0}$ ${\displaystyle Q=\infty }$

Известные результаты

В 1991 году Вайнбергер опубликовал подробный анализ ^[7] случая, когда и вклады в пригодность выбираются случайным образом. Позднее было показано, что его аналитическая оценка числа локальных оптимумов была ошибочной ^{[ требуется ссылка ]} . Однако численные эксперименты, включенные в анализ Вайнбергера, подтверждают его аналитический результат о том, что ожидаемая пригодность строки распределена нормально со средним значением приблизительно ${\displaystyle 1<<k\leq N}$

${\displaystyle \mu +\sigma {\sqrt {{2\ln(k+1)} \over {k+1}}}}$

и дисперсия приблизительно

${\displaystyle {{(k+1)\sigma ^{2}} \over {N[k+1+2(k+2)\ln(k+1)]}}}$.

Приложения

Модель NK нашла применение во многих областях, включая изучение спиновых стекол , коллективное решение проблем, ^[8] эпистаза и плейотропии в эволюционной биологии , а также комбинаторную оптимизацию .

Ссылки

1. Бороманд, Амин; Смальдино, Пол Э. (2023). «Предвзятость превосходства и шум в общении могут улучшить коллективное решение проблем». Журнал искусственных обществ и социального моделирования . 26 (3). doi : 10.18564/jasss.5154 .
2. Левинталь, ДА (1997). «Адаптация на пересеченной местности». Наука управления . 43 (7): 934–950. doi :10.1287/mnsc.43.7.934.
3. Кауфман, С.; Левин, С. (1987). «К общей теории адаптивных прогулок по пересеченной местности». Журнал теоретической биологии . 128 (1): 11–45. Bibcode : 1987JThBi.128...11K. doi : 10.1016/s0022-5193(87)80029-2. PMID  3431131.
4. Кауфман, С.; Вайнбергер, Э. (1989). «Модель NK пересеченных ландшафтов приспособленности и ее применение к созреванию иммунного ответа». Журнал теоретической биологии . 141 (2): 211–245. Bibcode : 1989JThBi.141..211K. doi : 10.1016/s0022-5193(89)80019-0. PMID  2632988.
5. Вайнбергер, Э. (1996), «NP-полнота модели Nk Кауфмана, настраиваемый неровный ландшафт приспособленности», рабочий документ Института Санта-Фе, 96-02-003.
6. Казначеев, Артем (2019). «Вычислительная сложность как предельное ограничение эволюции». Генетика . 212 (1): 245–265. doi :10.1534/genetics.119.302000. PMC 6499524. PMID  30833289 . 
7. Weinberger, Edward (15 ноября 1991 г.). «Локальные свойства модели Nk Кауфмана: настраиваемый неровный энергетический ландшафт». Physical Review A. 10. 44 (10): 6399–6413. Bibcode : 1991PhRvA..44.6399W. doi : 10.1103/physreva.44.6399. PMID  9905770.
8. Бороманд, А. и Смальдино, П.Е., 2021. Тяжелая работа, принятие риска и разнообразие в модели коллективного решения проблем. Журнал искусственных обществ и социального моделирования, 24(4).