Я знаю, что это несколько избитая тема, но я достиг предела помощи, которую я могу получить от того, на что уже был дан ответ.
Это для проблемы проекта Rosalind LREP. Я пытаюсь найти в строке самую длинную подстроку, состоящую из k, и мне предоставили дерево суффиксов, что очень удобно. Я знаю, что мне нужно аннотировать таблицу суффиксов количеством листьев-потомков от каждого узла, затем найти узлы с >=k потомками и, наконец, найти самый глубокий из этих узлов. Теоретически я готов.
Мне очень помогли следующие ресурсы (к сожалению, я могу опубликовать только 2):
Я могу получить пути от корня к каждому листу, но я не могу понять, как предварительно обработать дерево таким образом, чтобы я мог получить количество потомков от каждого узла. У меня есть отдельный алгоритм, который работает с небольшими последовательностями, но он имеет экспоненциальную сложность, поэтому для больших вещей он занимает слишком много времени. Я знаю, что с DFS я смогу выполнить всю задачу линейной сложности. Чтобы этот алгоритм работал, мне нужно иметь возможность получить самый длинный k-торф длиной ~ 40 000 строк менее чем за 5 минут.
Вот некоторые примеры данных (первая строка: sequence, вторая строка: k, формат таблицы суффиксов: parent child location length):
CATACATAC$
2
1 2 1 1
1 7 2 1
1 14 3 3
1 17 10 1
2 3 2 4
2 6 10 1
3 4 6 5
3 5 10 1
7 8 3 3
7 11 5 1
8 9 6 5
8 10 10 1
11 12 6 5
11 13 10 1
14 15 6 5
14 16 10 1
Результатом этого должно быть CATAC.
С помощью следующего кода (измененного из LiteratePrograms) я смог получить пути, но для более длинных последовательностей все еще требуется много времени, чтобы разобрать путь для каждого узла.
#authors listed at
#http://en.literateprograms.org/Depth-first_search_(Python)?action=history&offset=20081013235803
class Vertex:
def __init__(self, data):
self.data = data
self.successors = []
def depthFirstSearch(start, isGoal, result):
if start in result:
return False
result.append(start)
if isGoal(start):
return True
for v in start.successors:
if depthFirstSearch(v, isGoal, result):
return True
# No path was found
result.pop()
return False
def lrep(seq,reps,tree):
n = 2 * len(seq) - 1
v = [Vertex(i) for i in xrange(n)]
edges = [(int(x[0]),int(x[1])) for x in tree]
for a, b in edges:
v[a].successors.append(v[b])
paths = {}
for x in v:
result = []
paths[x.data] = []
if depthFirstSearch(v[1], (lambda v: v.data == x.data), result):
path = [u.data for u in result]
paths[x.data] = path
Что я хотел бы сделать, так это предварительно обработать дерево, чтобы найти узлы, которые удовлетворяют требованию descendants >= k, прежде чем находить глубину. Я еще даже не дошел до того, как буду вычислять глубину. Хотя я предполагаю, что у меня будет словарь, чтобы отслеживать глубину каждого узла в пути, а затем суммировать.
Итак, мой первый и самый важный вопрос: "Как выполнить предварительную обработку дерева с потомками листьев?"
Мой второй менее важный вопрос: "Как после этого я могу быстро вычислить глубину?"
P.S. Я должен заявить, что это не домашнее задание или что-то в этом роде. Я всего лишь биохимик, пытающийся расширить свой кругозор с помощью некоторых вычислительных задач.
