Описание каналов

			top

* * * * * * *		*

bottom

Канал описывается двумя последовательностями top и bottom, в которых размещаются верхние и нижние линейки контактных площадок каналов. Размер обеих последовательностей равен С – число колонок в канале

Множество цепей определяется как Net = {N₁, N₂, …, N_n} (n – это число цепей)

Пр.

top = {1, 0, 3, 1, 4, 2, 3, 2}; bottom = {6, 4, 6, 6, 3, 0, 5, 5}; n = 6; C = 8

Элемент 0 в top и bottom обозначают, свободный контакт на рисунке показан эскиз канала с разведенными цепями. Показан эскиз для хромосомы = (0, 0, 0) –

(см. ниже)

Горизонтальные и вертикальные ограничения

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

Вертикальные ограничения описываются ориентированным графом вертикальных ограничений (г.в.о.)

GV = {Enet, Ev}

Enet – множество вершин, соответствующих множеству цепей net

Ev – множество направляющих ребер.

Ребро (n, m) существует тогда, когда цепь n расположена выше цепи m для предотворощения наложения вертикальных сегментов цепей.

Для наших последовательностей г.в.о. на рис.:

рис. 2а

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

Далее будем использовать расширенный г.в.о. (р г.в.о.)

GRV = {Enet, Erv}

Enet – множество вершин, соответствующих множеству цепей net

Erv – множество направляющих ребер.

Ребро (n, m) принадлежащее Erv существует тогда, когда в г.в.о. существует путь из вершины n в m.

		рис. 2б

На рисунке 2а в г.в.о. есть путь из 4 в 5 через 3. Следовательно, в р.г.в.о. существует ребро (4, 5) и (4, 6)

Горизонтальные ограничения представлены не ориентированным графом гориз. огран. (г.г.о)

GН = {Enet, Eн}

Eн – множество ребер.

Ребро (n, m) принадлежащее Eн существует тогда, когда магистрали для n и m разнесены для исключения наложения горизонтальных сегментов n и m.

		рис. 2в

На рисунке 2в г.г.о. есть путь из 1 в 6, значит, что цепь 1 должны быть расположена выше 6, чтобы не было горизонтальных наложений. Цепи 1 и 5 могут быть расположены на одной магистрали. Цепь 1 и 2 тоже.

Дата добавления: 2015-08-21