- 期刊
The Duplication-loss Problem: Linear-time Algorithms for NNI Local Search
並列摘要
Given a set of gene trees, the DUPLICATION-LOSS problem is to infer a comparable species tree minimizing the number of gene duplications and losses (the mutation cost). This problem has been shown to be NP-hard. A standard heuristic performs the stepwise local searches on the tree space until a local minimum is reached. In this paper, we study the heuristic for the DUPLICATION-LOSS problem based on NNI local searches and propose a linear-time algorithm for the NNI LOCAL SEARCH problem under the mutation cost. Bansal et al. presented a near-linear time algorithm for the NNI LOCAL SEARCH problem under the duplication cost, and we also improve the result of Bansal et al. with a linear-time algorithm.
被引用紀錄
王紫雲（2008）。感光性水性PU的合成與性質研究〔碩士論文，中原大學〕。華藝線上圖書館。https://doi.org/10.6840/cycu200900646
Chen, C. Y. (2015). 偏好順序均為完整排列時之熱門配對集合研究 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2015.01570
延伸閱讀
- Xiang, M., Long, C., & Yu, G. (2012). Distributed Localization Algorithm based on Intersection and Exclusion. Research Journal of Applied Sciences, Engineering and Technology, 4(21), 4252-4257. https://www.airitilibrary.com/Article/Detail?DocID=20407467-201211-201512080011-201512080011-4252-4257
- Lin, B. S. (2005). Using Back-Propagation Neural Network for Automatic Wheezing Detection [doctoral dissertation, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2005.00326
- Yi, W. W. (2016). A Fast Local Search Algorithm for Virtual Network Embedding [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-0901201710385808
- HUR, S. W., & LILLIS, J. (2002). Relaxation and Clustering in a Local Search Framework: Application to Linear Placement. VLSI Design, 2002(), 143-154. https://doi.org/10.1080/10655140290010060
- 林志龍（2005）。Detection of duplicates in structured objects〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2005.00096