Cтр. 9

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

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

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

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

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

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

Литература

  • Компо Ф., Певзнер П. Реконструкция генома: головоломка из миллиарда кусочков // Журнал «Квант». 2014. № 3. Стр. 2—12.
  • Оре О. Графы и их применение. — М.: Мир, 1965.
  • Генкин С. А., Итенберг И. В., Фомин Д. В. Ленинградские математические кружки. — Киров, 1994. — [Главы «Графы-1» и Графы-2»].