Problem

Given a string ss having length nn, recall that its suffix tree T(s)T(s) is defined by the following properties:
- T(s)T(s) is a rooted tree having exactly nn leaves.
- Every edge of T(s)T(s) is labeled with a substring of s∗s∗, where s∗s∗ is the string formed by adding a placeholder symbol $ to the end of ss.
- Every internal node of T(s)T(s) other than the root has at least two children; i.e., it has degree at least 3.
- The substring labels for the edges leading down from a node to its children must begin with different symbols.
- By concatenating the substrings along edges, each path from the root to a leaf corresponds to a unique suffix of s∗s∗.
Figure 1 contains an example of a suffix tree.
Given: A DNA string ss of length at most 1kbp.
Return: The substrings of s∗s∗ encoding the edges of the suffix tree for ss. You may list these substrings in any order.
Sample Dataset
ATAAATG$
Sample Output
AAATG$
G$
T
ATG$
TG$
A
A
AAATG$
G$
T
G$
$
이 문제는 suffix tree의 모든 edge를 출력하는 문제이다. suffix tree는 모든 접미사들을 간단하게 표현하기 위해 만든 tree인데, 잘 살펴보면 일종의 trie 인것을 알 수 있다. Introdution to Patter Matching에서 살펴본 trie는 여러 개의 문자열을 나타닐때 최대한 겹치는 부분은 같이 표현하고 달라지는 부분은 갈라져서 그래프로 모든 문자열을 표현할 수 있게 해준다. suffix tree는 모든 접미사들을 달라지는 부분만 갈라져서 표현한단 점에서 같지만 trie는 edge 하나에 하나의 문자를, suffix tree는 edge 하나에 하나에서 여러개의 문자를 표현한단 점에서 다르다.
필자는 이 점을 고려하여, 첫번째로 모든 suffix를 구하고, 그 다음 그 suffix들로 trie를 만들고, 이 trie에서 edge들을 합쳐서 suffix tree의 edge를 구하는 방식을 취했다.
def making_suffs(seq):#모든 suffix구하기
suffs=[]
for i in range(len(seq)):
suffs.append(seq[i:])
return suffs
def building_trie(patterns):#trei만들기
trie={1:{}}#trie를 저장
node_id=1#새로운 노드 나타날시 노드id매겨주기
for pattern in patterns:#여러 문자열들 중 하나의 문자열
current_node = 1#일단 처음부터 시작
for char in pattern:#하나의 문자열에서 하나의 알파벳
if char in trie[current_node]:#지금 있는 노드에서 이 알파벳으로 이어진 노드가 있다면
current_node = trie[current_node][char]#지금 노드는 이어진 노드로 이동
else:#만약 없다면
node_id+=1#새로운 노드id 매기기
trie[current_node][char] = node_id#지금 노드와 새로운 노드 이어주기
current_node = node_id#지금 노드는 새로운 노드로
trie[node_id]={}#새로운 노드에서 이어지는 딕셔너리 만들기
return trie
def finding_edges(now_node,edge,graph):#edge만들기
if len(graph[now_node]) == 0:#leaf면
total_edge.append(edge)
return
if len(graph[now_node])>=2 and edge!='':#branching 이면
total_edge.append(edge)
edge=''
for k,v in graph[now_node].items():
finding_edges(v,edge+k,graph)
if __name__ == '__main__':
with open(r"파일경로",'r') as f:
seq = f.readline().rstrip()
total_edge=[]
suffs= making_suffs(seq)
trie=building_trie(suffs)
finding_edges(1,'',trie)
with open(r"파일경로",'w') as wf:
for i in total_edge:
print(i,file=wf)
ntroduction to Pattern Matching
Introduction to Pattern Matching ㅇ
'문제해결(PS) > ROSALIND' 카테고리의 다른 글
Counting Quartets (0) | 2024.12.17 |
---|---|
Character-Based Phylogeny (0) | 2024.12.17 |
Using the Spectrum Graph to Infer Peptides (0) | 2024.11.23 |
Quartets (0) | 2024.11.19 |
Matching a Spectrum to a Protein (1) | 2024.11.18 |