The Bottleneck Tree Alignment Problems

Given a set

W

of

k

sequences (strings) and a tree structure

T

with

k

leaves, each of which is labeled with a unique sequence in

W

, a

tree alignment

is to label a sequence to each internal node of

T

. The weight of an edge of the tree alignment is the distance, such as

Hamming

distance,

Levenshtein

(

edit

) distance or

reversal

distance, between the two sequences labeled to the two ends of the edge. The

bottleneck tree alignment problem

is to find a tree alignment such that the weight of the largest edge is minimized. A

lifted tree alignment

is a tree alignment, where each internal node

v

is labeled one of the sequences that was labeled to the children of

v

. The

bottleneck lifted tree alignment problem

is to find a lifted tree alignment such that the weight of the largest edge is minimized. In this paper, we show that the

bottleneck tree alignment problem

is NP-complete even when the tree structure is the binary tree and the weight function is

metric

. For special cases, we present an exact algorithm to solve the

bottleneck lifted tree alignment problem

in polynomial time. If the weight function is

ultrametric

, we show that any

lifted tree alignment

is an optimal

bottleneck tree alignment

.