ЛР / ЛР4 / graph_LR4

import random as rd
import numpy as np
import pandas as pd
import igraph as ig


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['label'] = weights
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]
# g.es["curved"] = True # кривизна ребер
ig.plot(g, bbox = (700, 700) # построение графика
, margin = 30
# , vertex_label_size = 10
, vertex_size = 40
, vertex_color = 'white')
return 1


def get_RNA_chain(size, elements = ['A', 'U', 'G', 'C']):
'''Возвращает цепочку РНК'''
return ''.join(rd.choice(elements) for i in range(size))

def pair_check(tup):
'''Проверяет пару на соединение'''
if tup in [('A', 'U'), ('U', 'A'), ('C', 'G'), ('G', 'C')]:
return True
return False

def initialize(size, rna, min_loop_length):
'''Заполняет матрицу для алгоритма Нуссиновой'''
mat = np.empty((size,size))
mat[:] = np.NAN
for i in range(size):
mat[i][i] = 0
if i > 0: mat[i][i-1] = 0
for k in range(1, size):
for i in range(size-k):
j = i + k
mat[i][j] = max([
mat[i+1][j]
, mat[i][j-1]
, mat[i+1][j-1] + 1 if pair_check((rna[i], rna[j])) else 0
, *[mat[i][t] + mat[t+1][j] for t in range(i+1, j-1)]
]) if j-i > min_loop_length else 0
return mat

def traceback(i, j, structure, mat, sequence, min_loop_length):
'''Находит наилучние пары'''
if j <= i: return # дошли до конца последовательности
# если j не является парным, при его удалении оценка не изменится, поэтому мы просто возвращаемся к следующему индексу
elif mat[i][j] == mat[i][j-1]:
traceback(i, j-1, structure, mat, sequence, min_loop_length)
# рассмотрим случаи, когда j образует пару.
else:
# попробуйте соединить j с соответствующим индексом k слева от него.
for k in [b for b in range(i, j-min_loop_length) if pair_check((sequence[b], sequence[j]))]:
# если оценка в i,j является результатом добавления 1 из спаривания (j,k) и любой оценки
# исходит из подструктуры слева от нее (i, k-1) и справа от нее (k+1, j-1)
if k-1 < 0:
if mat[i][j] == mat[k+1][j-1] + 1:
structure.append((k,j))
traceback(k+1, j-1, structure, mat, sequence, min_loop_length)
break
elif mat[i][j] == mat[i][k-1] + mat[k+1][j-1] + 1:
# добавляем пару (j,k) в наш список пар
structure.append((k,j))
# переместить рекурсию к двум подструктурам, образованным этой парой
traceback(i, k-1, structure, mat, sequence, min_loop_length)
traceback(k+1, j-1, structure, mat, sequence, min_loop_length)
break

def write_structure(sequence, structure):
'''Создает представление сворачивания цепочки'''
dot_bracket = ["." for _ in range(len(sequence))]
for s in structure:
dot_bracket[min(s)] = "("
dot_bracket[max(s)] = ")"
return "".join(dot_bracket)

def nussinov_algorithm(sequence, min_loop_length = 1):
'''Алгоритм Нуссиновой'''
size = len(sequence)
mat = initialize(size, sequence, min_loop_length)
structure = []
traceback(0,size-1, structure, mat, sequence, min_loop_length)
return (structure, mat, write_structure(sequence, structure))

def get_adj_mat_by_sequence(sequence):
'''Создание матрицы смежности по графа по переданной последовательности'''
num_seq = [i+'('+str(n)+')' for n, i in enumerate(sequence)]
result = nussinov_algorithm(sequence)
print('Заполненная матрица алгоритма Нуссиновой:\n', pd.DataFrame(result[1], columns=num_seq, index=num_seq)
, '\n\nПердставление свернутой цепочки: ', result[2]
, '\nМеста соединения цепочки: ', *result[0])
size = len(sequence)
adj_mat = [[1 if row-col == 1 or col-row == 1 else 0 for col in range(size)] for row in range(size)]
print('\nМатрица смежности исходного графа (невзвешенный неориентированный граф вида цепочка):', pd.DataFrame(adj_mat, columns=num_seq, index=num_seq), sep='\n')
view_graph(adj_mat, num_seq)
for i in result[0]: adj_mat[i[0]][i[1]] = adj_mat[i[1]][i[0]] = 9
print('\nМатрица смежности полученного графа (невзвешенный неориентированный граф вида цепочка):', pd.DataFrame(adj_mat, columns=num_seq, index=num_seq), sep='\n')
view_graph(adj_mat, num_seq)
return adj_mat


def main():
# rna = get_RNA_chain(10)
# rna = 'CUGGGCAACUUCACA' # тестовый пример
# rna = input('Задайте последовательность цепочки РНК: ')
rna = 'CAUGCUCUUU'
print('rna: ', rna)
get_adj_mat_by_sequence(rna)
return 1

if __name__ == "__main__": main()