On the bottleneck tree alignment problems

uTaipei > College of Science > Department of Computer Science > Periodical Articles > Item 987654321/16011

Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16011

Title:	On the bottleneck tree alignment problems
Authors:	Chen, Yen-Hung;陳彥宏;Tang, Chuan-Yi
Contributors:	臺北市立教育大學資訊科學系
Date:	2010-06
Issue Date:	2017-07-31 13:51:13 (UTC+8)
Abstract:	Given a set W of k sequences and a tree T with k leaves labeled with a unique sequence in W, a label tree is used to assign a sequence label to each internal node of the tree T. The cost of a tree edge is defined as the distance, such as the Hamming distance or the Levenshtein (edit) distance, between the sequence labels of a pair of nodes in the edge. The bottleneck edge of a label tree is the edge with the maximum cost in the label tree. The bottleneck tree alignment problem is concerned with the determination of a label tree with minimum cost of the bottleneck edge. A lifted label tree is a label tree in which the sequence label of each internal node is equal to the sequence label of some child of the node. The bottleneck lifted tree alignment problem involves the minimization of cost of the bottleneck edge among all possible lifted label trees of the tree T. This paper shows that when the distance function is a metric, the bottleneck tree alignment problem is NP-complete even when the tree structure resembles a binary tree. For special cases, an exact algorithm is used to solve the bottleneck lifted tree alignment problem in polynomial time. A 2(h-1)-approximation algorithm is used to solve the bottleneck tree alignment problem, where h is the height of the tree T. It is observed that the bound is existentially tight. Finally, this paper shows that any lifted label tree is an optimal solution to the bottleneck tree alignment problem if the distance function is an ultrametric.
Relation:	Information Sciences
Appears in Collections:	[Department of Computer Science] Periodical Articles

Files in This Item:

There are no files associated with this item.

Loading...