On the bottleneck tree alignment problems

University of Taipei > 理學院 > 資訊科學系 > 期刊論文 > Item 987654321/16011

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16011

题名:	On the bottleneck tree alignment problems
作者:	Chen, Yen-Hung;陳彥宏;Tang, Chuan-Yi
贡献者:	臺北市立教育大學資訊科學系
日期:	2010-06
上传时间:	2017-07-31 13:51:13 (UTC+8)
摘要:	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.
關聯:	Information Sciences
显示于类别:	[資訊科學系] 期刊論文

文件中的档案:

没有与此文件相关的档案.

在uTaipei中所有的数据项都受到原著作权保护.

数据加载中.....