Distances in Trees

곰탱이장 2024. 9. 24. 18:58

ROSALIND | Distances in Trees

It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Distances in Trees solved by 1148 2012년 8월 7일 12:00:00 오전 by Rosalind Team Topics: Phylogeny Paths in Trees For any two nodes of a tree

rosalind.info

Problem

Figure 1. This tree can be represented in Newick format in a number of ways, including (C, D, (A, B)); (A, (D, C), B); and (((A, B), C), D);.

Newick format is a way of representing trees even more concisely than using an adjacency list, especially when dealing with trees whose internal nodes have not been labeled.

First, consider the case of a rooted tree $T$ . A collection of leaves $v_{1}, v_{2}, \dots, v_{n}$ of $T$ are neighbors if they are all adjacent to some internal node $u$ . Newick format for $T$ is obtained by iterating the following key step: delete all the edges ${v_{i}, u}$ from $T$ and label $u$ with $(v_{1}, v_{2}, \dots, v_{n}) u$ . This process is repeated all the way to the root, at which point a semicolon signals the end of the tree.

A number of variations of Newick format exist. First, if a node is not labeled in $T$ , then we simply leave blank the space occupied by the node. In the key step, we can write $(v_{1}, v_{2}, \dots, v_{n})$ in place of $(v_{1}, v_{2}, \dots, v_{n}) u$ if the $v_{i}$ are labeled; if none of the nodes are labeled, we can write $(,, \dots,)$ .

A second variation of Newick format occurs when $T$ is unrooted, in which case we simply select any internal node to serve as the root of $T$ . A particularly peculiar case of Newick format arises when we choose a leaf to serve as the root.

Note that there will be a large number of different ways to represent $T$ in Newick format; see Figure 1.

Given: A collection of $n$ trees ( $n \leq 40$ ) in Newick format, with each tree containing at most 200 nodes; each tree $T_{k}$ is followed by a pair of nodes $x_{k}$ and $y_{k}$ in $T_{k}$ .

Return: A collection of $n$ positive integers, for which the $k$ th integer represents the distance between $x_{k}$ and $y_{k}$ in $T_{k}$ .

Sample Dataset

(cat)dog;
dog cat

(dog,cat);
dog cat

Sample Output

1 2

이 문제는 Newick 형식으로 작성된 트리에서 주어진 두 노드 간의 거리를 구하는 문제이다. Newick 형식이란 트리를 나타내는 형식 중 하

나이다. 괄호 안에 묶인 인자들은 괄호 뒤에 바로 붙은 인자를 뿌리로 연결되어 있는 노드들이다. 두 노드 간의 거리란 일종의 가장 짧은 공유 노드를 찾는 느낌이다. 나와 친척간에 촌을 따질 때 공유된 조상을 찾아 내가 쭈욱 올라가다 조상을 만나고 다시 쭈욱 내려가서 친척을 찾아서 촌수를 따지는 감각이다. 그러므로 거리를 구할 떄는 )는 조상까지 올라가는 감각이고 (는 조상을 만나 내려가는 감각이다. 그러므로 일종의 a))))))조상((((b 같은 식으로 연결된다. 저러한 식으로 문자열을 조정하면 구할 수 있는 문제이다.

def distnace(s,x,y):
    x_index = s.find(x)
    y_index = s.find(y)
    new_s = [i for i in s[min(x_index,y_index):max(x_index,y_index)] if i in [')','(',',']]#사이만 따지기
    ans_s=''
    for k in new_s:문자열로 조정
        ans_s+=k
    while '(,)' in ans_s:#'(,)' 는 내려갔다 바로 올라오는 무의미이므로 삭제
        ans_s=ans_s.replace('(,)','')

    if ans_s.count(')') == len(ans_s):#서로 직계
        return len(ans_s)
    elif ans_s.count('(') == len(ans_s):#서로 직계
        return len(ans_s)
    elif ans_s.count(',') == len(ans_s):#서로 같은 조상 공유 즉 형제?
        return 2
    else:
        return ans_s.count('(') + ans_s.count(')') + 2 # 올라갔다 내려왔다


if __name__=="__main__":
    wr_file=open(r'파일경로','w')
    ans=[]
    with open(r"파일경로",'r') as pylo:
        trees=[line.strip().replace(';','') for line in pylo.readlines() if len(line.strip()) > 0]
    for i in range(0,len(trees),2):
        handle=trees[i]
        x,y = trees[i+1].split(' ')
        ans.append(str(distnace(handle,x,y)))
    wr_file.write(' '.join(ans))

    print('end')

필자는 이 문제를 풀 때 인터넷에서 도움을 받아 풀어, 개인적으로는 처음에 복잡하게 생각한 문제인거 같다.