계통수와 공통 조상

계산 분자생물학(computational molecular biology)에서는 여러 작업 가운데 유전 서열을 처리하는 일을 다룬다. 두 서열의 진화적 관계를 생각할 때, 두 서열의 차이가 크지 않으면 서로 가깝게 관련되어 있다고 말한다. 이러한 관계는 조상의 서열을 후손의 서열 위쪽에 배치하는 트리로 나타낼 수 있으며, 이런 트리를 계통수(phylogenetic tree) 라고 부른다.

계통학의 한 과제는 주어진 서열들로부터 트리를 추론하는 것이지만, 여기서는 문제를 단순화하여 트리 구조를 고정한다. 트리는 완전 이진 트리(complete binary tree) 이다. 트리의 잎(leaf) $n$개가 주어지며, $n$은 항상 2의 거듭제곱이다. 각 잎은 아미노산 서열이고, 아래 표에 있는 한 글자 코드로 표기한다. 모든 서열의 길이는 $l$로 같다. 비용이 최소가 되는 공통 조상의 서열을 구하는 것이 목표이다.

비용은 다음과 같이 정의한다. 트리의 모든 내부 노드에는 길이 $l$의 서열이 붙는다. 한 간선의 비용은 그 양 끝 서열이 서로 다른 위치의 개수(해밍 거리)이고, 전체 비용은 트리의 모든 간선 비용의 합이다. 모든 잎의 공통 조상 서열은 루트에 있는 서열이다. 최적 공통 조상이란 전체 비용이 최소가 되는 공통 조상을 말한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 $n$과 $l$로 시작하며, 각각 잎 서열의 개수와 서열의 길이를 뜻한다. 입력은 $n = l = 0$인 줄로 끝나고, 이 줄은 처리하지 않는다. 그 외에는 $1 \le n \le 1024$($n$은 2의 거듭제곱)이고 $1 \le l \le 1000$이다. 이어서 아미노산 알파벳으로 이루어진 길이 $l$의 단어 $n$개가 주어지며, 이들은 완전 이진 트리의 잎을 왼쪽에서 오른쪽 순서로 나열한 것이다.

각 테스트 케이스마다 한 줄을 출력한다. 사전순으로 가장 작은 최적 공통 조상 서열을 출력하고, 공백 하나를 둔 뒤 최소 전체 비용을 출력한다.

최소 비용을 달성하는 공통 조상 서열이 여러 개일 수 있으므로, 답이 유일하도록 그중 사전순으로 가장 작은 서열(아미노산 한 글자 코드를 알파벳 순서로 비교)로 고정한다. 최소 전체 비용 자체는 항상 유일하다.