Sé que este es un tema un tanto trillado, pero he llegado al límite de ayuda que puedo obtener de lo que ya se ha respondido.

Esto es para elProblema del proyecto Rosalind LREP. Estoy tratando de encontrar la subcadena k-peated más larga en una cadena y he estadoprevisto El árbol del sufijo, que es bonito. Sé que necesito anotar la tabla de sufijos con el número de hojas descendientes de cada nodo, luego encontrar los nodos con>=k descendientes, y finalmente encontraremos el más profundo de esos nodos. En teoría, estoy listo.

He recibido mucha ayuda de los siguientes recursos (oops, solo puedo publicar 2):

Puedo obtener las rutas desde la raíz a cada hoja, pero no puedo averiguar cómo preprocesar el árbol de tal manera que pueda obtener el número de descendientes de cada nodo. Tengo un algoritmo separado que funciona en secuencias pequeñas pero está en complejidad exponencial, por lo que para cosas más grandes toma demasiado tiempo. Sé que con un DFS debería poder realizar toda la tarea en complejidad lineal. Para que este algoritmo funcione, tengo que ser capaz de obtener la turba k más larga de una cadena de aproximadamente 40,000 en menos de 5 minutos.

Aquí hay algunos datos de muestra (primera línea:sequence, segunda linea:k, formato de tabla de sufijos: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

El resultado de esto debería serCATAC.

Con el siguiente código (modificado deProgramas de alfabetización) He podido obtener las rutas, pero aún así toma mucho tiempo en secuencias más largas analizar una ruta para cada nodo.

#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

Lo que me gustaría hacer es preprocesar el árbol para encontrar nodos que satisfagan losdescendants >= k Requisito previo a la búsqueda de la profundidad. Ni siquiera he llegado a saber cómo voy a calcular la profundidad todavía. Aunque imagino que tendré un diccionario para realizar un seguimiento de las profundidades de cada nodo en la ruta y luego las sumas.

Entonces, mi primera pregunta más importante es:"¿Cómo preprocesé el árbol con hojas descendientes?"

Mi segunda pregunta menos importante es:"Después de eso, ¿cómo puedo calcular rápidamente la profundidad?"

PD Debería decir que estono es tarea o cualquier cosa de ese tipo. Solo soy un bioquímico que intenta expandir mis horizontes con algunos desafíos computacionales.