유전자 나무는 다양한 유전자 또는 생물 종의 진화를 보여주는 나무입니다. 유전자 나무는 잎 노드에 저장된 특정 유전자들의 관련성을 조상에 대한 가정 없이 나타냅니다. 잎 노드는 분류군이라고 하는 유전자를 나타내고, 내부 노드는 추정 조상 분류군을 나타냅니다. 나무의 각 모서리는 계통 발생 길이라는 양의 정수와 연관되어 있으며, 이는 모서리의 두 노드 사이의 진화적 거리를 정량화합니다. 예를 들어, 아래 왼쪽 그림은 6개의 잎 노드로 구성된 유전자 나무를 보여주는데, 이는 6개 분류군 간의 관계를 근사적으로 나타내며, 오른쪽 그림은 4개 분류군으로 구성된 유전자 나무를 보여줍니다.

위의 T1과 T2 트리처럼, 유전자 트리는 뿌리가 없는 트리로 모델링되며, 각 내부 노드(잎이 아닌 노드)는 3차수를 갖습니다. 두 잎 노드 사이의 경로 길이는 두 노드 사이의 고유한 경로를 따라 있는 변의 계통발생학적 길이의 합입니다. T1에서 인간과 소 사이의 경로 길이는 2 + 3 = 5이고, 인간과 금붕어 사이의 경로 길이는 2 + 4 + 8 + 10 = 24입니다. 이 길이는 인간이 금붕어보다 소에 유전적으로 훨씬 더 가깝다는 것을 나타냅니다. T2를 통해 인간과 가장 가까운 영장류는 침팬지라고 추측할 수 있습니다.

연구자들은 유전자 계통수에서 유전자 사이의 거리를 측정하는 데 관심을 두고 있습니다. 유명한 거리 측정법은 모든 무순서 잎 쌍의 경로 길이의 제곱의 합입니다. 더 정확하게 말하면, 이러한 거리 d(T)는 다음과 같이 정의됩니다.

여기서 pu,v는 T의 두 리프 노드 u와 v 사이의 경로 길이입니다. d(T)는 T의 모든 순서 없는 리프 쌍 u와 v에 대한 경로 길이 p2u,v의 제곱의 합입니다. 그림 B.1의 유전자 트리 T2의 경우 모든 순서 없는 리프 쌍에 대한 경로는 (인간, 침팬지), (인간, 고릴라), (인간, 오랑우탄), (침팬지, 고릴라), (침팬지, 오랑우탄), (고릴라, 오랑우탄)의 여섯 개입니다. 경로 길이의 제곱의 합은 22 + 42 + 52 + 42 + 52 + 52 = 111이므로 d(T2) = 111입니다.

뿌리가 없는 유전자 트리 T가 주어졌을 때, d(T)를 출력하는 프로그램을 작성하세요.

#4385 upload 12 done 2 how_to_reg 2

Gene Tree timer 1s memory 512MB

#4385

Gene Tree 1s 512MB