Creating a Character Table

https://rosalind.info/problems/ctbl/

ROSALIND | Creating a Character Table

Problem

Given a collection of nn taxa, any subset SS of these taxa can be seen as encoding a character that divides the taxa into the sets SS and ScSc; we can represent the character by S∣ScS∣Sc, which is called a split. Alternately, the character can be represented by a character array AA of length nn for which A[j]=1A[j]=1 if the jjth taxon belongs to SS and A[j]=0A[j]=0 if the jjth taxon belongs to ScSc (recall the "ON"/"OFF" analogy from “Counting Subsets”).

At the same time, observe that the removal of an edge from an unrooted binary tree produces two separate trees, each one containing a subset of the original taxa. So each edge may also be encoded by a split S∣ScS∣Sc.

A trivial character isolates a single taxon into a group of its own. The corresponding split S∣ScS∣Sc must be such that SS or ScSc contains only one element; the edge encoded by this split must be incident to a leaf of the unrooted binary tree, and the array for the character contains exactly one 0 or exactly one 1. Trivial characters are of no phylogenetic interest because they fail to provide us with information regarding the relationships of taxa to each other. All other characters are called nontrivial characters (and the associated splits are called nontrivial splits).

A character table is a matrix CC in which each row represents the array notation for a nontrivial character. That is, entry Ci,jCi,j denotes the "ON"/"OFF" position of the iith character with respect to the jjth taxon.

Given: An unrooted binary tree TT in Newick format for at most 200 species taxa.

Return: A character table having the same splits as the edge splits of TT. The columns of the character table should encode the taxa ordered lexicographically; the rows of the character table may be given in any order. Also, for any given character, the particular subset of taxa to which 1s are assigned is arbitrary.

Sample Dataset

(dog,((elephant,mouse),robot),cat);

Sample Output

00110
00111

 

 이 문제는 Newick 형식으로 주어진 unrooted binary tree에서 charactor table을 구하는 문제이다. 이 문제를 풀기 위해선 위의 설명에 나온 여러 개념들을 이해해야한다.

 먼저 split이란 전체 집합에서 특정 subset S와 그의 여집합인 Sc를 가르는 선? 개념으로 이해하면 된다. S|Sc에서 |이 split이다. charactor array란 n개의 길이의 특정 배열 A에서 j가 S에 속한다면 A[j]=1, j가 Sc에 속한다면 즉 S에 속하지 않는다면 A[j]=0임을 나타낸 array이다. 즉 특정 element의 S에 속함 여부를 나타내는 배열이라고 생각하면 된다. 

 그리고 unrooted binary tree에서 특정 edge를 없앤다면, 두 개의 개별적인 트리가 나타나는데 이 관계를 S와 S의 여집합 같은 split 개념으로 볼 수 있다.

 trivial charactor(하찮은 특징?)은 저렇게 갈랐을 때 S 집합에 하나의 원소만이 존재하여 가른 edge가 terminal node에 바로 닿아있고 array가 단 하나의 1이나 단 하나의 0만을 가질 때를 말한다. 이런 경우는 계통학적으로 의미가 없으므로 이러하지 않은 nontrivial charactor가 중요하다.

 이제 charactor table은 저러한 charactor table의 모임인데, 이 경우 가르는 곳이 다른 것을 row로, 각 원소를 column으로 하는 2차원 배열이다.

 

 이제 개념설명이 끝났다. 우리학 구하고픈 바는 Newick 형식에서 nontrivial charctor만 모아 charactor table을 출력하는 것이다. nontirivial charactor는 일종의 internal node를 기준으로 공통의 조상을 가지냐 마느냐로 구할 수 있다. 

 필자는 복잡한 Newick 형식을 곧이곧대로 raw한 데이터로 풀 자신이 없어 Biopython의 Phylo 모듈을 쓰기로 하였다. Phylo 모듈에서 필자가 헷갈린 점은 clade class는 node가 아니라 그 아래의 관계까지 포함된 작은 tree class라는 것이다. 그 외 자세한 설명은 코드를 통해 하도록 하겠다.

from Bio import Phylo
import copy
tree = Phylo.read(r"파일경로",'newick')#트리 일기

new_tree = copy.deepcopy(tree)#복사 안해도 상관 없지만 불안해서
non_ter_nodes = new_tree.get_nonterminals()#internal node들 뽑기

ter_nodes=new_tree.get_terminals()#terminal node들 뽑기
ter_len=len(ter_nodes)

char=[]#terminal node들의 이름 저장
for ter_node in ter_nodes:
    char.append(ter_node.name)
char.sort()#알파벳순으로

char_table={}#사실상 array임
for name in char:
    char_table[name] = 0#알파벳 순으로 0 연결

f=open(r"파일경로",'w')
for non_ter_node in non_ter_nodes:#internal node들 중 하나의 clade 뽑기
    now_char_table = char_table.copy()#딕셔너리 복사
    group=non_ter_node.get_terminals()#이 clade에 속한 터미널 노드들
    if len(group) != ter_len:#모든 터미널 노드 속하지 않으면
        for node in group:
            now_char_table[node.name] = 1#노드 이름 보고 S에 속한다보기
        #이렇게 만든 table을 출력하기
        print(''.join(map(str,list(now_char_table.values()))),file=f)

예시에서의 internal node는 3개이다. 가장 왼쪽의 dog,cat,그리고 분류군이 있는거 1개, 그리고 그림에 나타난 2개이다. 가장 첫번째 internal node는 전체를 포함하는 trivial charactor가 되어버리므로 패스하고, 안의 저 두개의 internal node를 공통 조상으로 하는 것들을 1로 하는 식의 array를 만들면 된다.