請使用永久網址來引用或連結此文件:
https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/120035
|
| 題名: | A property tester for tree-likeness of quartet topologies |
| 作者: | Chang, Maw-Shang;Lin, Chuang-Chieh;Rossmanith, Peter |
| 關鍵詞: | Randomized algorithm;Property testing;Evolutionary tree;Quartet consistency |
| 日期: | 2010-07-09 |
| 上傳時間: | 2021-03-05 12:12:45 (UTC+8) |
| 摘要: | Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0<ε<1, by examining function values of f over o(|D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε|D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f Q , which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f Q satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f Q . In this paper, we prove the existence of a set of quartet topologies of error number at least c(n4) for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n 3/ε) queries, and is of one-sided error and non-adaptive. |
| 關聯: | Theory of Computing Systems 49, pp.576–587 |
| DOI: | 10.1007/s00224-010-9276-5 |
| 顯示於類別: | [資訊工程學系暨研究所] 期刊論文
|
文件中的檔案:
| 檔案 |
描述 |
大小 | 格式 | 瀏覽次數 |
|---|
| index.html | | 0Kb | HTML | 65 | 檢視/開啟 |
|
在機構典藏中所有的資料項目都受到原著作權保護.
|