Я знаю, что это несколько запутанная тема, но я достиг предела помощи, которую я могу получить от того, что »С уже ответили.

Это дляРозалинд проект проблемы LREP, Я'я пытаюсь найти самую длинную k-peated подстроку в строке, и я 'былпредоставлена суффикс дерева, что приятно. Я знаю, что мне нужно аннотировать таблицу суффиксов числом выходов из каждого узла, а затем находить узлы с>=k потомки, и, наконец, найти самые глубокие из этих узлов. По теории яя поставил

Мы получили большую помощь от следующих ресурсов (к сожалению, я могу только опубликовать 2):

Я могу получить пути от корня до каждого листа, но я могуНе могу понять, как предварительно обработать дерево таким образом, чтобы я мог получить количество потомков от каждого узла. У меня есть отдельный алгоритм, который работает на небольших последовательностях, но этос экспоненциальной сложностью, поэтому для больших вещей это занимает слишком много времени. Я знаю, что с DFS я должен быть в состоянии выполнить всю задачу в линейной сложности. Чтобы этот алгоритм работал, мне нужно иметь возможность получить самый длинный k-торф из строки длиной ~ 40000 менее чем за 5 минут.

Вот's некоторые примеры данных (первая строка: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 Требование до нахождения глубины. У меня нетдаже не понял, как яЯ собираюсь вычислить глубину еще. Хотя я представляюУ меня будет некоторый словарь для отслеживания глубины каждого узла в пути, а затем суммы.

Итак, мой первый самый важный вопрос:Как мне предварительно обработать дерево потомками? "

Мой второй менее важный вопрос:После этого, как я могу быстро вычислить глубину? "

Постскриптум Я должен заявить, что этоне домашнее задание или что-то в этом роде. Я'Я просто биохимик, пытающийся расширить свой кругозор с помощью некоторых вычислительных задач.