| Testing consistency of quartet topologies: a parameterized approach | |
|---|---|
| 學年 | 102 |
| 學期 | 1 |
| 出版（發表）日期 | 2013-11-30 |
| 作品名稱 | Testing consistency of quartet topologies: a parameterized approach |
| 作品名稱（其他語言） | |
| 著者 | Maw-Shang Chang; Chuang-Chieh Lin; Peter Rossmanith |
| 單位 | |
| 出版者 | |
| 著錄名稱、卷期、頁數 | Information Processing Letters 113(22-24), pp. 852-857 |
| 摘要 | Property testing considers the following task: given a function ψ over a domain D, a property P and a parameter 0 < \epsilon < 1, by querying function values of f over o(|D|) elements in D, determine if ψ satisfies P or differs from any one which satisfies P in at least \epsilon |D| elements. We focus on consistency of quartet topologies. Given a set Q of quartet topologies over an n-taxon set and an upper bound k on the number of quartets whose topologies are missing, we present a non-adaptive property tester with one-sided error, which runs in time O(1.7321^k kn^3/\epsilon) and uses queries, to test if Q is consistent with an evolutionary tree. |
| 關鍵字 | Randomized algorithm;Property testing;Evolutionary tree;Quartet method |
| 語言 | en_US |
| ISSN | 1872-6119 |
| 期刊性質 | 國外 |
| 收錄於 | SCI |
| 產學合作 | |
| 通訊作者 | Chuang-Chieh Lin |
| 審稿制度 | 是 |
| 國別 | USA |
| 公開徵稿 | |
| 出版型式 | ,電子版,紙本 |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/120034 ) |
| SDGS | 優質教育 |
GoogleAnalytics