A Property Tester for Tree-Likeness of Quartet Topologies View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2010-07-09

AUTHORS

Maw-Shang Chang, Chuang-Chieh Lin, Peter Rossmanith

ABSTRACT

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 fQ, which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that fQ satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with fQ. In this paper, we prove the existence of a set of quartet topologies of error number at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c{n\choose 4}$\end{document} for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n3/ε) queries, and is of one-sided error and non-adaptive. More... »

PAGES

576-587

References to SciGraph publications

  • 1990-09. Analysis of binary trees when occasional multifurcations can be considered as aggregates of bifurcations in BULLETIN OF MATHEMATICAL BIOLOGY
  • 2009-01-27. New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem in THEORY OF COMPUTING SYSTEMS
  • 2006-01-01. Homomorphisms in Graph Property Testing in TOPICS IN DISCRETE MATHEMATICS
  • 1998. From Quartets to Phylogenetic Trees in SOFSEM’ 98: THEORY AND PRACTICE OF INFORMATICS
  • 1999. Quartet Cleaning: Improved Algorithms and Simulations in ALGORITHMS - ESA’ 99
  • 1992-01. The complexity of reconstructing trees from qualitative characters and subtrees in JOURNAL OF CLASSIFICATION
  • 2001. Property Testing in HANDBOOK OF RANDOMIZED COMPUTING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-010-9276-5

    DOI

    http://dx.doi.org/10.1007/s00224-010-9276-5

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1048682896


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chang", 
            "givenName": "Maw-Shang", 
            "id": "sg:person.013174232477.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan", 
              "id": "http://www.grid.ac/institutes/grid.412047.4", 
              "name": [
                "Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lin", 
            "givenName": "Chuang-Chieh", 
            "id": "sg:person.013577077462.41", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577077462.41"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52056, Aachen, Germany", 
              "id": "http://www.grid.ac/institutes/grid.1957.a", 
              "name": [
                "Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52056, Aachen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rossmanith", 
            "givenName": "Peter", 
            "id": "sg:person.013545320167.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013545320167.55"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00224-009-9165-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045232696", 
              "https://doi.org/10.1007/s00224-009-9165-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49477-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035836541", 
              "https://doi.org/10.1007/3-540-49477-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48481-7_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034130792", 
              "https://doi.org/10.1007/3-540-48481-7_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4615-0013-1_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1089738653", 
              "https://doi.org/10.1007/978-1-4615-0013-1_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02462102", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053384231", 
              "https://doi.org/10.1007/bf02462102"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-33700-8_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014702965", 
              "https://doi.org/10.1007/3-540-33700-8_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02618470", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015721561", 
              "https://doi.org/10.1007/bf02618470"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010-07-09", 
        "datePublishedReg": "2010-07-09", 
        "description": "Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function\u00a0f over a domain D, a property \u2118 and a parameter 0<\u03b5<1, by examining function values of\u00a0f over\u00a0o(|D|) elements in\u00a0D, determine whether f satisfies \u2118 or differs from any one which satisfies \u2118 in at least \u03b5|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 fQ, which assigns one of the three possible topologies for every quartet over an n-taxon set\u00a0S. We say that fQ satisfies tree-likeness if there exists an evolutionary tree\u00a0T whose induced quartet topologies coincide with\u00a0fQ. In this paper, we prove the existence of a set of quartet topologies of error number at least \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$c{n\\choose 4}$\\end{document} for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n3/\u03b5) queries, and is of one-sided error and non-adaptive.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-010-9276-5", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "49"
          }
        ], 
        "keywords": [
          "theoretical computer science", 
          "quartet topologies", 
          "computer science", 
          "one-sided error", 
          "tree construction", 
          "property tester", 
          "topology", 
          "error number", 
          "following tasks", 
          "task", 
          "function values", 
          "possible topologies", 
          "algorithm", 
          "queries", 
          "combinatorial properties", 
          "property testing", 
          "satisfies", 
          "evolutionary tree construction", 
          "tester", 
          "set", 
          "error", 
          "input function", 
          "trees", 
          "parameter 0", 
          "elements", 
          "construction", 
          "evolutionary tree", 
          "science", 
          "domain D", 
          "number", 
          "testing", 
          "field", 
          "function", 
          "properties", 
          "values", 
          "existence", 
          "differs", 
          "coincide", 
          "quartet", 
          "paper", 
          "taxa", 
          "quartet topologies coincide", 
          "topology coincide", 
          "first property tester", 
          "Tree-Likeness"
        ], 
        "name": "A Property Tester for Tree-Likeness of Quartet Topologies", 
        "pagination": "576-587", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048682896"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-010-9276-5"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-010-9276-5", 
          "https://app.dimensions.ai/details/publication/pub.1048682896"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:14", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/article/article_514.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-010-9276-5"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9276-5'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9276-5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9276-5'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9276-5'


     

    This table displays all metadata directly associated to this object as RDF triples.

    148 TRIPLES      22 PREDICATES      77 URIs      62 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-010-9276-5 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N6076221a83434297955932b713cf9612
    4 schema:citation sg:pub.10.1007/3-540-33700-8_17
    5 sg:pub.10.1007/3-540-48481-7_28
    6 sg:pub.10.1007/3-540-49477-4_3
    7 sg:pub.10.1007/978-1-4615-0013-1_15
    8 sg:pub.10.1007/bf02462102
    9 sg:pub.10.1007/bf02618470
    10 sg:pub.10.1007/s00224-009-9165-y
    11 schema:datePublished 2010-07-09
    12 schema:datePublishedReg 2010-07-09
    13 schema:description 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 fQ, which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that fQ satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with fQ. In this paper, we prove the existence of a set of quartet topologies of error number at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$c{n\choose 4}$\end{document} for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n3/ε) queries, and is of one-sided error and non-adaptive.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N77fc7215c159420794133c6c053b445f
    18 Nca96ebfaa4634bb4a28bf30260dbc66f
    19 sg:journal.1052098
    20 schema:keywords Tree-Likeness
    21 algorithm
    22 coincide
    23 combinatorial properties
    24 computer science
    25 construction
    26 differs
    27 domain D
    28 elements
    29 error
    30 error number
    31 evolutionary tree
    32 evolutionary tree construction
    33 existence
    34 field
    35 first property tester
    36 following tasks
    37 function
    38 function values
    39 input function
    40 number
    41 one-sided error
    42 paper
    43 parameter 0
    44 possible topologies
    45 properties
    46 property tester
    47 property testing
    48 quartet
    49 quartet topologies
    50 quartet topologies coincide
    51 queries
    52 satisfies
    53 science
    54 set
    55 task
    56 taxa
    57 tester
    58 testing
    59 theoretical computer science
    60 topology
    61 topology coincide
    62 tree construction
    63 trees
    64 values
    65 schema:name A Property Tester for Tree-Likeness of Quartet Topologies
    66 schema:pagination 576-587
    67 schema:productId N958335dbac6847b6af3a6ea716596459
    68 Nd6b6f3922b9144a1be00368aef14c788
    69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048682896
    70 https://doi.org/10.1007/s00224-010-9276-5
    71 schema:sdDatePublished 2021-11-01T18:14
    72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    73 schema:sdPublisher N9c8e84b203184eb2a4044923230e87c5
    74 schema:url https://doi.org/10.1007/s00224-010-9276-5
    75 sgo:license sg:explorer/license/
    76 sgo:sdDataset articles
    77 rdf:type schema:ScholarlyArticle
    78 N6076221a83434297955932b713cf9612 rdf:first sg:person.013174232477.45
    79 rdf:rest Naa66ff79305a40f6a06ca5281fe76c88
    80 N77fc7215c159420794133c6c053b445f schema:volumeNumber 49
    81 rdf:type schema:PublicationVolume
    82 N958335dbac6847b6af3a6ea716596459 schema:name doi
    83 schema:value 10.1007/s00224-010-9276-5
    84 rdf:type schema:PropertyValue
    85 N9c8e84b203184eb2a4044923230e87c5 schema:name Springer Nature - SN SciGraph project
    86 rdf:type schema:Organization
    87 Naa66ff79305a40f6a06ca5281fe76c88 rdf:first sg:person.013577077462.41
    88 rdf:rest Nb270694a30754dcbb98c69818e67dc17
    89 Nb270694a30754dcbb98c69818e67dc17 rdf:first sg:person.013545320167.55
    90 rdf:rest rdf:nil
    91 Nca96ebfaa4634bb4a28bf30260dbc66f schema:issueNumber 3
    92 rdf:type schema:PublicationIssue
    93 Nd6b6f3922b9144a1be00368aef14c788 schema:name dimensions_id
    94 schema:value pub.1048682896
    95 rdf:type schema:PropertyValue
    96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Information and Computing Sciences
    98 rdf:type schema:DefinedTerm
    99 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    100 schema:name Artificial Intelligence and Image Processing
    101 rdf:type schema:DefinedTerm
    102 sg:journal.1052098 schema:issn 1432-4350
    103 1433-0490
    104 schema:name Theory of Computing Systems
    105 schema:publisher Springer Nature
    106 rdf:type schema:Periodical
    107 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
    108 schema:familyName Chang
    109 schema:givenName Maw-Shang
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
    111 rdf:type schema:Person
    112 sg:person.013545320167.55 schema:affiliation grid-institutes:grid.1957.a
    113 schema:familyName Rossmanith
    114 schema:givenName Peter
    115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013545320167.55
    116 rdf:type schema:Person
    117 sg:person.013577077462.41 schema:affiliation grid-institutes:grid.412047.4
    118 schema:familyName Lin
    119 schema:givenName Chuang-Chieh
    120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577077462.41
    121 rdf:type schema:Person
    122 sg:pub.10.1007/3-540-33700-8_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014702965
    123 https://doi.org/10.1007/3-540-33700-8_17
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/3-540-48481-7_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034130792
    126 https://doi.org/10.1007/3-540-48481-7_28
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/3-540-49477-4_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035836541
    129 https://doi.org/10.1007/3-540-49477-4_3
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-1-4615-0013-1_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089738653
    132 https://doi.org/10.1007/978-1-4615-0013-1_15
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/bf02462102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053384231
    135 https://doi.org/10.1007/bf02462102
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/bf02618470 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015721561
    138 https://doi.org/10.1007/bf02618470
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/s00224-009-9165-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1045232696
    141 https://doi.org/10.1007/s00224-009-9165-y
    142 rdf:type schema:CreativeWork
    143 grid-institutes:grid.1957.a schema:alternateName Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52056, Aachen, Germany
    144 schema:name Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52056, Aachen, Germany
    145 rdf:type schema:Organization
    146 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan
    147 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan
    148 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...