‍От прогулок по Кёнигсбергу до реконструкции генома

Современ­ная био­логия ещё не может «про­чи­тать» большие моле­кулы ДНК как книгу, «буква за бук­вой». Вме­сто этого учё­ные расшиф­ро­вы­вают после­до­ва­тель­но­сти корот­ких кусоч­ков ДНК, не зная, из какого места генома был выре­зан дан­ный кусо­чек. Процесс сборки генома из огром­ного числа таких кусоч­ков, полу­чен­ных из большого числа копий одной ДНК, назы­ва­ется секве­ни­ро­ва­нием (от английского слова sequence — после­до­ва­тель­ность). Этот процесс сродни попытке собрать пазл из мил­ли­арда кусоч­ков и осно­вы­ва­ется на раз­ви­тии одной матема­ти­че­ской тео­рии, заро­дившейся три сто­ле­тия назад.

Пер­вая поло­вина XVIII века. Вели­кий матема­тик Лео­нард Эйлер решает «задачу о кёнигсберг­ских мостах» — дока­зы­вает, что в Кёнигсберге, рас­по­ложен­ном на берегах реки и двух её ост­ро­вах, нельзя было пройти по каж­дому из семи мостов, суще­ство­вавших в то время, ровно один раз и вер­нуться после этого в исход­ную точку. Подоб­ный путь на соот­вет­ствующем графе назы­ва­ется эйле­ро­вым цик­лом. У задачи о суще­ство­ва­нии эйле­рова цикла кри­те­рий раз­решимо­сти очень про­стой — из каж­дой вершины графа должно выхо­дить чёт­ное число рёбер. Да и задача нахож­де­ния эйле­рова цикла (ЗЭЦ) реша­ется отно­си­тельно быстро даже для очень большого графа.

Вто­рая поло­вина XIX века. Матема­тик Уильям Гамильтон рас­смат­ри­вает внешне похожую на ЗЭЦ задачу: найти на графе замкну­тый путь (гамильто­нов цикл), про­хо­дящий через каж­дую вершину по одному разу (ЗГЦ).

Вто­рая поло­вина XX века. Было уста­нов­лено, что ЗГЦ (в отли­чие от ЗЭЦ) явля­ется пред­ста­ви­те­лем класса задач, для кото­рых эффек­тив­ные алго­ритмы реше­ния неиз­вестны.

Конец XX века — XXI век. В сере­дине 1990‐х годов был секве­ни­ро­ван геном бак­те­рии, в 2001 году — чело­века. Работа была дли­тель­ной и дорого­сто­ящей, так как алго­ритмы супер­компью­те­ров осно­вы­ва­лись на ЗГЦ. В послед­нее деся­ти­ле­тие матема­ти­ками были раз­ра­бо­таны быст­ро­действующие методы сборки, свя­зан­ные с ЗЭЦ, и теперь био­логи гото­вятся к реше­нию фун­дамен­таль­ной задачи: для каж­дого вида мле­копи­тающих про­ве­сти сборку генома.