On the bottleneck tree alignment problems

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

請使用永久網址來引用或連結此文件: 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中所有的資料項目都受到原著作權保護.

資料載入中.....