A property tester for tree-likeness of quartet topologies

doi:10.1007/s00224-010-9276-5

淡江大學機構典藏 > 工學院 > 資訊工程學系暨研究所 > 期刊論文 > Item 987654321/120035

請使用永久網址來引用或連結此文件: 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	24	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....