[진화] 계통학을 표현하는 Newick Tree Format

The Newick Tree Format

이 글은 http://evolution.genetics.washington.edu/phylip/newicktree.html 에서 발췌 번역한 것 입니다.

소  개

컴퓨터가 읽을 수 있는 trees를 대표하는 형식인 Newick Standard는 1857년 영국의 유명한 수학자 Arthur Cayley가 고안하였고, trees에 나오는 인자들과 중접된 괄호를 사용합니다.

만약에 우리가 이런 rooted tree를 가지고 있다고 하면:

이 tree는 이런 형태의 인화할 수 있는 문자로 나타낼 수 있습니다.

(B,(A,C,E),D);

 

Tree의 끝은 세미콜론으로 끝납니다. 이 tree의 가장 아래 있는 node는 tip이 아니라 가장 안에 있는 interior node입니다. Interior node들은 한 쌍의 일치하는 중첩된 괄호에 의해 나타내집니다. 이들 사이에 있는 것들은 node들을 나타내는 것으로, 콤마들로 나뉘어져 있고, 그 internal node에서 직접적으로 유래된 것들 입니다. 위의 tree를 예제로 들면, 두 번째 interior node의 즉각적인 후손은 B와 D 입니다. 다른 interior node도 한 쌍의 괄호로 나타내고 있고, 즉각적인 후손인 A, C, E를 포함하고 있습니다. 우리의 예제에서 A, B, C, D, E는 tip들을 나타냅니다, 하지만 일반적으로는 이들 또한 중첩된 괄호의 사용으로 인해 interior node들이 될 수 있습니다.

Tip들은 이들의 이름으로 표기됩니다. 이름은 어떤 인쇄할 수 있는 문자열이 되어도 상관 없지만, 공백, 콜론, 세미콜론, 괄호, 대괄호 등은 사용할 수 없습니다.

 

이름안에 공백을 넣기를 원하는 사람도 있음으로, 언더스코어("_")를 공백으로 가정합니다. 이름 안에 있는 언더스코어는 공백으로 처리되어 읽힙니다. 이름이 없는 트리도 있을 수 있습니다.

(,(,,),); 은 허용이 됩니다.  Tree들은 어떤 단계에서든지 가지가 3개이상으로 나뉠 수 있습니다 (multifurcating).

 

Brach의 길이는 Tree안에 실수 또는 소수로 집어 넣을 수 있습니다. 길이는 node 다음에 콜론 다음에 위치합니다. 이것은 그 node밑에 즉각적으로 있는 branch의 길이를 대표합니다. 그러므로 위의 예제 tree의 길이들은 이렇게 나타낼 수 있습니다.

(B:6.0,(A:5.0,C:3.0,E:4.0):5.0,D:11.0);

 

Tree는 파일 가장 첫 번째 줄에서 시작합니다. 그리고 다음 줄로 지속해서 나타낼 수 있습니다. 긴 Tree에서는 콤마 다음이라면 적어도 Tree를 새 줄에서 시작하는 것이 최선의 방법입니다. 공백은 아무 곳이나 삽입될 수 있는데, 종의 이름 가운데나, branch의 길이 사이에는 올 수 없습니다.

위의 묘사는 사실 Newick Standard의 부분 집합입니다. 예를 들어 interior node들은 이름을 가질 수 있고, 이러한 이름들은 올바른 괄호를 따라야 합니다.

(B:6.0,(A:5.0,C:3.0,E:4.0)Ancestor1:5.0,D:11.0);

 

예  제

트리 형태를 이해시켜드리기 위한 예제들 입니다.

1. ((너구리:19.19959,곰:6.80041):0.84600,((물범:11.99700, 물개:12.00300):7.52973,((원숭이:100.85930,고양이:47.14069):20.59201, 족제비:18.87953):2.09460):3.87382,개:25.46154);




2. (Bovine:0.69395,(Gibbon:0.36079,(Orang:0.33636,(Gorilla:0.17147,(Chimp:0.19268, Human:0.11927):0.08386):0.06124):0.15057):0.54939,Mouse:1.21460):0.10;




3. (Bovine:0.69395,(Hylobates:0.36079,(Pongo:0.33636,(G._Gorilla:0.17147, (P._paniscus:0.19268,H._sapiens:0.11927):0.08386):0.06124):0.15057):0.54939, Rodent:1.21460);




4. A;




5. ((A,B),(C,D));




6. (Alpha,Beta,Gamma,Delta,,Epsilon,,,);

 

(Non-)Uniqueness

Newick Standard는 두 가지 이유로 하나의 tree만 특별하게 대표하지 않습니다.

첫 번째, 생물학적으로 흥미롭지 않아도, node의 후손들의 왼쪽에서 오른쪽 순서는 표현에 영향을 미칩니다. 그러므로 생물학자에게…

(A,(B,C),D);

는 아래와 같고

(A,(C,B),D);

도 아래와 같고

(D,(C,B),A);

이것도 아래와 같고

(D,A,(C,B));

마찬가지로 아래와 같습니다.

((C,B),A,D);

 

Rooted와 unrooted trees

더하여, Newick standard는 rooted tree를 표현합니다. 많은 생물학적 이유들 때문에 우리는 root의 위치를 추론할 수 없습니다. 우리는 이러한 경우들을 추론하기 위해서 unrooted tree를 사용하기를 원합니다. 여기에서의 관습은 간단하게 임의로 tree의 root 정하고 거기에 따른 rooted tree의 결과를 보고하는 것 입니다. 그러므로

(B,(A,D),C);

는 밑의 unrooted tree와 같고

(A,(B,C),D);

밑의 tree와도 같습니다.

((A,D),(C,B));

 

광범위한 사용

비특징적인 한계에도 불구하고 tree에 대한 가독성과 tree 파일을 읽을 수 있는 프로그램 코딩의 쉬운점은 광범위한 사용에서도 위의 표준을 지키게 했습니다.

Newick standard의 경쟁자들은 NEXUS standard를 포함한 여러 가지가 있습니다. 하지만 NEXUS도 Newick standard를 기반으로 하고 있습니다. (NEXUS tree들에서 Newick tree를 찾을 수 있답니다.)

Newick 기반이 좀 더 낮은 표준은 PhyloXML standard가 있습니다. 이것은 괄호대신 중첩된 한 쌍의 <CLADE> ...< /CLADE> 태그를 사용하여 표현합니다.

기원

Newick Standard는 1986년 6월 26일 Durham, New Hampshire에서 개최한 Society for the Study of Evolution 미팅의 비공식적인 위원회 미팅에서 채택되었습니다. 이러한 이름이 채택된 이유는 Dover, New Hampshire에 위치한 Newick’s restaurant에서 위원들이 바닷가재 요리를 맛있게 먹었기 때문입니다. Tree 형식은 1984년 Christopher Meacham에 의해 개발되었습니다. 그는 Seattle에 있는 동안 PHYLIP package를 위해서 tree plotting programs을 만들었습니다. 그가 Seattle을 방문한 이유는 University of Georgia에서 안식년을 맞아 간거였고, 그러므로 간접적으로 일부 펀딩을 받았습니다.

 

Newick Standard의 다른 표현들

아직 Newick standard의 정식 출판은 없었습니다. 하지만…

- Gary Olsen이 만든 정식 표현은 여기에 있습니다.

- 위키피디아에서의 Newick Standard 페이지가 여기 있습니다.