Approximation Algorithms for Bounded Degree Phylogenetic Roots View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-10-19

AUTHORS

Zhi-Zhong Chen

ABSTRACT

The Degree-ΔClosest Phylogenetickth Root Problem (ΔCPRk) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E⊕{{u,v} : u,v are leaves of T and dT(u,v)≤k}|, is minimized, where dT(u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for ΔCPR2 for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR3, and a polynomial-time approximation scheme for the maximization version of ΔCPRk for any fixed Δ and k. More... »

PAGES

1-23

References to SciGraph publications

  • 2000. Phylogenetic k-Root and Steiner k-Root in ALGORITHMS AND COMPUTATION
  • 1998-05-29. An empirical comparison of heuristic methods for creating maximally diverse groups in JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • 2004-07. Correlation Clustering in MACHINE LEARNING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-007-9072-z

    DOI

    http://dx.doi.org/10.1007/s00453-007-9072-z

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
              "id": "http://www.grid.ac/institutes/grid.412773.4", 
              "name": [
                "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chen", 
            "givenName": "Zhi-Zhong", 
            "id": "sg:person.015654265661.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1023/b:mach.0000033116.57574.95", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005313049", 
              "https://doi.org/10.1023/b:mach.0000033116.57574.95"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1057/palgrave.jors.2600510", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039273292", 
              "https://doi.org/10.1057/palgrave.jors.2600510"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-40996-3_46", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028915527", 
              "https://doi.org/10.1007/3-540-40996-3_46"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007-10-19", 
        "datePublishedReg": "2007-10-19", 
        "description": "Abstract\nThe Degree-\u0394Closest Phylogenetickth Root Problem (\u0394CPRk) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in\u00a0T is at least 3 and at most \u0394, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E\u2295{{u,v}\u00a0:\u00a0u,v are leaves of T and dT(u,v)\u2264k}|, is minimized, where dT(u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants \u0394,k such that either both \u0394\u22653 and k\u22653, or \u0394>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for \u0394CPR2 for any fixed \u0394>3, a quadratic-time 12-approximation algorithm for 3CPR3, and a polynomial-time approximation scheme for the maximization version of \u0394CPRk for any fixed \u0394 and k.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00453-007-9072-z", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "51"
          }
        ], 
        "keywords": [
          "important combinatorial optimization problem", 
          "polynomial time approximation scheme", 
          "combinatorial optimization problems", 
          "maximum matching problem", 
          "matching problem", 
          "approximation algorithm", 
          "approximation scheme", 
          "optimization problem", 
          "external nodes", 
          "maximization version", 
          "algorithm", 
          "internal nodes", 
          "nodes", 
          "theoretical study", 
          "constants \u03b4", 
          "number of disagreements", 
          "tree T.", 
          "problem", 
          "root problem", 
          "tree T", 
          "graph", 
          "NPs", 
          "scheme", 
          "T.", 
          "version", 
          "distance", 
          "number", 
          "evolutionary biology", 
          "phylogenetic roots", 
          "elements", 
          "degree", 
          "disagreement", 
          "roots", 
          "biology", 
          "study", 
          "leaves", 
          "paper"
        ], 
        "name": "Approximation Algorithms for Bounded Degree Phylogenetic Roots", 
        "pagination": "1-23", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1015638369"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-007-9072-z"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-007-9072-z", 
          "https://app.dimensions.ai/details/publication/pub.1015638369"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T09:55", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_433.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00453-007-9072-z"
      }
    ]
     

    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/s00453-007-9072-z'

    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/s00453-007-9072-z'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9072-z'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9072-z'


     

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

    107 TRIPLES      22 PREDICATES      65 URIs      54 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-007-9072-z schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Na9da9611bfc44073bb5fed65c65fc014
    4 schema:citation sg:pub.10.1007/3-540-40996-3_46
    5 sg:pub.10.1023/b:mach.0000033116.57574.95
    6 sg:pub.10.1057/palgrave.jors.2600510
    7 schema:datePublished 2007-10-19
    8 schema:datePublishedReg 2007-10-19
    9 schema:description Abstract The Degree-ΔClosest Phylogenetickth Root Problem (ΔCPRk) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E⊕{{u,v} : u,v are leaves of T and dT(u,v)≤k}|, is minimized, where dT(u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for ΔCPR2 for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR3, and a polynomial-time approximation scheme for the maximization version of ΔCPRk for any fixed Δ and k.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf Na77fc7d31baf4be590565936b3c6cc5e
    14 Nf5075fa631d44dcf8956331b487ded21
    15 sg:journal.1047644
    16 schema:keywords NPs
    17 T.
    18 algorithm
    19 approximation algorithm
    20 approximation scheme
    21 biology
    22 combinatorial optimization problems
    23 constants δ
    24 degree
    25 disagreement
    26 distance
    27 elements
    28 evolutionary biology
    29 external nodes
    30 graph
    31 important combinatorial optimization problem
    32 internal nodes
    33 leaves
    34 matching problem
    35 maximization version
    36 maximum matching problem
    37 nodes
    38 number
    39 number of disagreements
    40 optimization problem
    41 paper
    42 phylogenetic roots
    43 polynomial time approximation scheme
    44 problem
    45 root problem
    46 roots
    47 scheme
    48 study
    49 theoretical study
    50 tree T
    51 tree T.
    52 version
    53 schema:name Approximation Algorithms for Bounded Degree Phylogenetic Roots
    54 schema:pagination 1-23
    55 schema:productId N6f53c10a04cd4881a3f5780a7b5920e1
    56 Ne2248f0d1cbe47d3b40cd1db06fdb9d1
    57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015638369
    58 https://doi.org/10.1007/s00453-007-9072-z
    59 schema:sdDatePublished 2022-05-10T09:55
    60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    61 schema:sdPublisher Na69c00496c5d4286b8adf0a0e3e12fc9
    62 schema:url https://doi.org/10.1007/s00453-007-9072-z
    63 sgo:license sg:explorer/license/
    64 sgo:sdDataset articles
    65 rdf:type schema:ScholarlyArticle
    66 N6f53c10a04cd4881a3f5780a7b5920e1 schema:name doi
    67 schema:value 10.1007/s00453-007-9072-z
    68 rdf:type schema:PropertyValue
    69 Na69c00496c5d4286b8adf0a0e3e12fc9 schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 Na77fc7d31baf4be590565936b3c6cc5e schema:volumeNumber 51
    72 rdf:type schema:PublicationVolume
    73 Na9da9611bfc44073bb5fed65c65fc014 rdf:first sg:person.015654265661.98
    74 rdf:rest rdf:nil
    75 Ne2248f0d1cbe47d3b40cd1db06fdb9d1 schema:name dimensions_id
    76 schema:value pub.1015638369
    77 rdf:type schema:PropertyValue
    78 Nf5075fa631d44dcf8956331b487ded21 schema:issueNumber 1
    79 rdf:type schema:PublicationIssue
    80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Information and Computing Sciences
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Computation Theory and Mathematics
    85 rdf:type schema:DefinedTerm
    86 sg:journal.1047644 schema:issn 0178-4617
    87 1432-0541
    88 schema:name Algorithmica
    89 schema:publisher Springer Nature
    90 rdf:type schema:Periodical
    91 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
    92 schema:familyName Chen
    93 schema:givenName Zhi-Zhong
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
    95 rdf:type schema:Person
    96 sg:pub.10.1007/3-540-40996-3_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028915527
    97 https://doi.org/10.1007/3-540-40996-3_46
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1023/b:mach.0000033116.57574.95 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005313049
    100 https://doi.org/10.1023/b:mach.0000033116.57574.95
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1057/palgrave.jors.2600510 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039273292
    103 https://doi.org/10.1057/palgrave.jors.2600510
    104 rdf:type schema:CreativeWork
    105 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
    106 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
    107 rdf:type schema:Organization
     




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


    ...