1298. Phylogenetic Trees Inherited

Among other things, Computational Molecular Biology deals with processing genetic sequences. Considering the evolutionary relationship of two sequences, we can say that they are closely related if they do not differ very much. We might represent the relationship by a tree, putting sequences from ancestors above sequences from their descendants. Such trees are called phylogenetic trees.

Whereas one task of phylogenetics is to infer a tree from given sequences, we’ll simplify things a bit and provide a tree structure - this will be a complete binary tree. You’ll be given the n leaves of the tree. Sure you know, n is always a power of 2. Each leaf is a sequence of amino acids (designated by the one-character-codes you can see in the figure). All sequences will be of equal length l. Your task is to derive the sequence of a common ancestor with minimal costs.

Amino Acid

Alanine Ala A

Arginine Arg R

Asparagine Asn N

Aspartic Acid Asp D

Cysteine Cys C

Glutamine Gln Q

Glutamic Acid Glu E

Glycine Gly G

Histidine His H

Isoleucine Ile I

Amino Acid

Leucine Leu L

Lysine Lys K

Methionine Met M

Phenylalanine Phe F

Proline Pro P

Serine Ser S

Threonine Thr T

Tryptophan Trp W

Tyrosine Tyr Y

Valine Val V

The costs are determined as follows: every inner node of the tree is marked with a sequence of length l, the cost of an edge of the tree is the number of positions at which the two sequences at the ends of the edge differ, the total cost is the sum of the costs at all edges. The sequence of a common ancestor of all sequences is then found at the root of the tree. An optimal common ancestor is a common ancestor with minimal total costs.