6.24. Генетическая задача

Бенцер [2] сформулировал следующую задачу о возможных соединениях, допустимых конфигурацией химических компонент генов. Если такими компонентами являются трехмерные молекулы, то они могут быть соединены вместе в соответствии с определенной структурой. Это объединение может быть представлено в трехмерном пространстве, если каждой молекуле поставлена в соответствие некоторая вершина и вершины соединены прямыми линиями при наличии связи между соответствующими молекулами. Возникает вопрос, можно ли расположить молекулы на одной и той же прямой линии так, чтобы они сохранили прежние связи? Каждая молекула представляется при этом отрезком прямой. Если пара молекул связана, то соответствующие им отрезки взаимно перекрываются. Таким образом, задача состоит в нахождении условий, при которых граф связей можно представить с помощью пересекающихся определенным образом отрезков одной прямой линии, т. е. необходимо так сопоставить отрезки с вершинами, чтобы два отрезка пересекались тогда и только тогда, когда они соответствуют смежным вершинам. Граф, который может быть представлен таким образом, будет называться графом отрезков. Например, треугольник можно представить на действительной оси перекрывающимися отрезками и С другой стороны, цикл, состоящий более чем из трех вершин, не может быть представлен рассматриваемым способом.

Было показано [59], что если граф не содержит ни одного из пяти типов подграфов, представленных на рис. 6.57 (т. е. имеющих только те связи между вершинами, которые показаны на рисунке), то он может быть изображен с помощью отрезков на прямой.

Биологическая задача в ее общем виде связана с мутантными генами. Требуется проверить соответствие линейной модели гена заданной информации о пересечении (соединении) пар.

Фалкерсои и Гросс показали, что задача определения графа отрезков является частным случаем следующей задачи, которую они решили: дана матрица А (т. е. матрица, элементы которой равны или 1).

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

Рис. 6.57,

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

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

Применительно к графу отрезков матрица А должна рассматриваться как матрица инциденций доминирующих клик. (Множество вершин, каждая пара которых.

соединена ребром, называется кликой графа. Если семейство всех таких множеств вершин частично упорядочено по множеству включений, то максимальные элементы называются доминирующими кликами графа. Учитывая, что две вершины связаны ребром тогда и только тогда, когда они принадлежат некоторой доминирующей клике, можно считать, что матрица инцидеиций доминирующих клик полностью определяет граф.) В результате граф является графом отрезков тогда и только тогда, когда единичные элементы во всех столбцах матрицы инцидеиций доминирующей клики расположены последовательно друг за другом. Гилмор и Гофман [31] доказали, что граф является графом отрезков тогда и только тогда, когда каждая квадратная решетка в имеет диагональ и каждый цикл нечетной длины в дополнительном графе имеет треугольную хорду. Треугольная хорда цикла, проходящего через вершины есть любое ребро или