ГУАП
КАФЕДРА № 41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
ассистент |
|
|
|
М.Н. Шелест |
|
|
|
|
|
|
|
|
|
|
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №4
СПЕЦИАЛЬНЫЕ АЛГОРИТМЫ НА ГРАФАХ
по курсу: ПОСТРОЕНИЕ И АНАЛИЗ ГРАФОВЫХ МОДЕЛЕЙ
РАБОТУ ВЫПОЛНИЛ СТУДЕНТ ГР. №
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2022
Цель работы
Реализовать и проверить на тестовом примере специальный алгоритм на графе.
Индивидуальный вариант
Задание согласно индивидуальному варианту №10 в соответствии с
таблицей 1.
Таблица 1 – Задание индивидуального варианта
№ варианта |
Алгоритм |
Алгоритм Нуссиновой
Исходные данные: невзвешенный неориентированный граф
10
вида цепочки, в состав которого входят вершины 4 типов (2 пары противоположностей)
2
Ход работы
1) Написали подпрограмму, реализующую отображение графа на экране. Функция view_graph для отображения графа на экране. Список использованных переменных в соответствии с таблицей 3, код в соответствии с листингом 1. Результат работы функций в соответствии с рисунком 1.
Таблица 3 – Список переменных подпрограммы из Листинга 1
Название |
|
|
|
|
Значение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
adj_mat |
Матрица смежности |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
||
peaks |
Список вершин |
|
|
|
|
|
|
|
||
|
|
|
|
|||||||
curved_value |
Тип отображения связей (прямые или округлие) |
|
|
|||||||
|
|
|
|
|
|
|
|
|
||
g |
Объект графа |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
||
list_edges |
Список ребер |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|||
weights |
Список весов ребер |
|
|
|
|
|
|
|||
|
|
|
|
|
||||||
Листинг 1 – Подпрограмма отображения графа на экране |
|
|
|
|||||||
|
|
|||||||||
def view_graph(adj_mat, peaks = [], curved_value = False): |
|
|||||||||
if not peaks: peaks = list(adj_mat) |
|
|
|
|
||||||
g = ig.Graph() |
# создание ориентированного графа |
|
||||||||
g.add_vertices(len(peaks)) |
# добавление вершин графа |
|
||||||||
for i in range(len(g.vs)): |
|
|
|
|
|
|
||||
g.vs[i]["id"]= peaks[i] if isinstance(peaks[i], int) |
||||||||||
else i |
|
|
|
|
|
|
|
|
|
|
g.vs[i]["label"]= peaks[i] |
|
|
|
|
|
|||||
list_edges = [(row, col) for col in range(len(adj_mat)) for |
||||||||||
row in range(len(adj_mat)) if adj_mat[row][col]] |
|
|
|
|||||||
g.add_edges(list_edges) |
|
|
|
|
|
|
|
|||
weights = [adj_mat[row][col] for col in range(len(adj_mat)) |
||||||||||
for row in range(len(adj_mat)) if adj_mat[row][col]] |
|
|
||||||||
g.es['edge_width'] = weights |
|
|
|
|
|
|
||||
g.es["curved"] = curved_value |
# кривизна ребер |
|
|
|||||||
edges |
= |
[adj_mat[row][col] |
== |
9 |
for |
col |
in |
|||
range(len(adj_mat)) |
for |
row |
in |
range(len(adj_mat)) |
if |
|||||
adj_mat[row][col]] |
|
|
|
|
|
|
|
|
||
g.es["color"] = ['red' if i else 'black' for i in edges] |
|
|||||||||
ig.plot(g, bbox = (700, 700) |
|
# построение графика |
|
|||||||
,margin = 30
,vertex_size = 40
,vertex_color = 'white') return 1
3
Рисунок 1 – Результат работы функции view_graph
4
2) Самостоятельно составили и визуализировали невзвешенный неориентированный граф вида цепочка. Граф представляет собой цепочку вершин, каждая из которых именуется одной из 4 возможных букв в соответствии с рисунком 2-3.
Рисунок 2 – Представление графа в виде матрицы смежности
Рисунок 3 – Изображение графа
5
3)Описание алгоритма Нуссиновой.
Алгоритм Нуссиновой — это алгоритм прогнозирования структуры нуклеиновой кислоты, используемый в вычислительной биологии для прогнозирования свертывания молекулы РНК, который использует принципы динамического программирования.
Основная идея: максимизация числа спаренных оснований.
Исходный данные: последовательность символов (A, U, G, C)
Выполним проход алгоритма на примере графа, созданного нами раннее в данной работе.
Сначала заполняется матрица позволяющая определить самое большое кол-во спаренных оснований. Чтобы ее заполнить сначала инициируется нулями основная диагональ и та, что под ней в соответствии с рисунком 4.
Рисунок 4 – Инициализация матрицы
6
Затем выполняется проход по диагоналям вверх от основной с заполнением элементов матрицы на основе уже имеющихся данных. Для определения значения текущего элемента матрицы используется формула в соответствии с рисунком 5. Где F(i,j) – это значение из матрицы в точке (i,j), а s(i,j) – это проверка могул ли вершины с индексами i и j сочетаться,
допускаются пары (A-U) и (G-C), если пара соответствует перечисленным то s(i,j) равно 1 иначе 0.
Рисунок 5 – Формула определения значения элемента матрицы Так проходя по матрице, мы ее постепенно заполняем в соответствии с
рисунком 6 и в итоге получаем заполненную матрицу в соответствии с рисунком 7.
Рисунок 6 – Этапы заполнения матрицы
7
Рисунок 7 – Результат заполнения матрицы Теперь, когда мы заполнили матрицу мы проходим по ней в обратном
порядке начиная с правого верхнего угла. Пользуясь формулой в соответствии с рисунком 5, определяем какие переходы увеличивают количество пар.
Проход дает нам пары (3, 6) и (1, 7) в соответствии с рисунком 8.
Рисунок 8 – Обратный проход по матрице
8
Добавим связи (3, 6) и (1, 7) в матрицу смежности исходного графа в соответствии с рисунком 9.
Рисунок 9 – Результат заполнения матрицы смежности Изобразим получившийся граф в соответствии с рисунком 10
Рисунок 10 – Итоговый граф
9
4)Блок-схема алгоритма в соответствии с рисунком 11.
Рисунок 11 – Блок-схема алгоритма
10