Repetição repetida mais longa (k vezes)
Eu sei que este é um tópico um pouco batido, mas eu alcancei o limite de ajuda que posso obter do que já foi respondido.
Isto é para oProblema do projeto Rosalind LREP. Eu estou tentando encontrar a mais longa subcorrente k-peated em uma corda e eu estiveforneceu a árvore do sufixo, o que é legal. Eu sei que preciso anotar a tabela de sufixos com o número de folhas descendentes de cada nó e, em seguida, localizar nós com>=k
descendentes e, finalmente, encontrar o mais profundo desses nós. Teoria-sábio estou definido.
Eu recebi muita ajuda dos seguintes recursos (oops, só posso postar 2):
Encontre a sequência repetitiva mais longa em uma stringPesquisa em profundidade (Python)Eu posso obter os caminhos da raiz para cada folha, mas não consigo descobrir como pré-processar a árvore de forma que eu possa obter o número de descendentes de cada nó. Eu tenho um algoritmo separado que funciona em pequenas seqüências, mas é em complexidade exponencial, por isso, para coisas maiores, leva muito tempo. Eu sei que com um DFS eu deveria ser capaz de executar toda a tarefa em complexidade linear. Para que esse algoritmo funcione, eu preciso ser capaz de obter a maior k-turfa de uma cadeia de comprimento de ~ 40.000 em menos de 5 minutos.
Aqui estão alguns dados de amostra (primeira linha:sequence
, segunda linha:k
, formato de tabela de sufixo: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
A saída disso deve serCATAC
.
Com o seguinte código (modificado deLiteratePrograms) Consegui obter os caminhos, mas ainda leva muito tempo em sequências mais longas para analisar um caminho para cada nó.
#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
O que eu gostaria de fazer é pré-processar a árvore para encontrar nós que satisfaçamdescendants >= k
exigência antes de encontrar a profundidade. Eu nem cheguei a como vou calcular a profundidade ainda. Embora eu imagine que terei algum dicionário para acompanhar as profundidades de cada nó no caminho, então soma.
Então, minha primeira pergunta mais importante é:"Como faço para pré-processar a árvore com folhas descendentes?"
Minha segunda questão menos importante é:"Depois disso, como posso calcular rapidamente a profundidade?"
P.S. Eu devo afirmar que issonão é lição de casa ou qualquer coisa desse tipo. Eu sou apenas um bioquímico tentando expandir meus horizontes com alguns desafios computacionais.