New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2009-01-27

AUTHORS

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

ABSTRACT

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4kn+n4). In this paper, first we present an O(3.0446kn+n4) fixed-parameter algorithm and an O(2.0162kn3+n5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O*((1+ε)k) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant. More... »

PAGES

342-367

References to SciGraph publications

  • 1999. Quartet Cleaning: Improved Algorithms and Simulations in ALGORITHMS - ESA’ 99
  • 2005. A Lookahead Branch-and-Bound Algorithm for the Maximum Quartet Consistency Problem in ALGORITHMS IN BIOINFORMATICS
  • 1992-01. The complexity of reconstructing trees from qualitative characters and subtrees in JOURNAL OF CLASSIFICATION
  • 1999. Parameterized Complexity in NONE
  • 1998. From Quartets to Phylogenetic Trees in SOFSEM’ 98: THEORY AND PRACTICE OF INFORMATICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-009-9165-y

    DOI

    http://dx.doi.org/10.1007/s00224-009-9165-y

    DIMENSIONS

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


    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/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/978-1-4612-0515-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050354225", 
              "https://doi.org/10.1007/978-1-4612-0515-9"
            ], 
            "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"
          }, 
          {
            "id": "sg:pub.10.1007/11557067_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049532580", 
              "https://doi.org/10.1007/11557067_6"
            ], 
            "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"
          }
        ], 
        "datePublished": "2009-01-27", 
        "datePublishedReg": "2009-01-27", 
        "description": "Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over\u00a0S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4kn+n4). In this paper, first we present an O(3.0446kn+n4) fixed-parameter algorithm and an O(2.0162kn3+n5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O*((1+\u03b5)k) fixed-parameter algorithm, where \u03b5>0 is an arbitrarily small constant.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-009-9165-y", 
        "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": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "47"
          }
        ], 
        "keywords": [
          "fixed-parameter algorithm", 
          "inconsistency problem", 
          "quartet topologies", 
          "parameter algorithm", 
          "algorithm", 
          "small constant", 
          "topology", 
          "set", 
          "parameter k", 
          "trees", 
          "evolutionary tree", 
          "subset", 
          "news", 
          "time", 
          "constants", 
          "problem", 
          "taxa", 
          "paper", 
          "quartet topologies Q", 
          "topologies Q", 
          "Minimum Quartet Inconsistency (MQI) problem", 
          "Quartet Inconsistency (MQI) problem", 
          "parameterized MQI problem", 
          "MQI problem"
        ], 
        "name": "New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem", 
        "pagination": "342-367", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045232696"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-009-9165-y"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-009-9165-y", 
          "https://app.dimensions.ai/details/publication/pub.1045232696"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-11-01T18:13", 
        "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_489.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-009-9165-y"
      }
    ]
     

    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-009-9165-y'

    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-009-9165-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-009-9165-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-009-9165-y'


     

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

    119 TRIPLES      22 PREDICATES      54 URIs      41 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-009-9165-y schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N2894472c972c4d57a472ef344dde5451
    4 schema:citation sg:pub.10.1007/11557067_6
    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-4612-0515-9
    8 sg:pub.10.1007/bf02618470
    9 schema:datePublished 2009-01-27
    10 schema:datePublishedReg 2009-01-27
    11 schema:description Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4kn+n4). In this paper, first we present an O(3.0446kn+n4) fixed-parameter algorithm and an O(2.0162kn3+n5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O*((1+ε)k) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf Nae9c686f983647d6b154a8fc4950ae59
    16 Ndd6d9fc1fd6443a889a758ea180d278d
    17 sg:journal.1052098
    18 schema:keywords MQI problem
    19 Minimum Quartet Inconsistency (MQI) problem
    20 Quartet Inconsistency (MQI) problem
    21 algorithm
    22 constants
    23 evolutionary tree
    24 fixed-parameter algorithm
    25 inconsistency problem
    26 news
    27 paper
    28 parameter algorithm
    29 parameter k
    30 parameterized MQI problem
    31 problem
    32 quartet topologies
    33 quartet topologies Q
    34 set
    35 small constant
    36 subset
    37 taxa
    38 time
    39 topologies Q
    40 topology
    41 trees
    42 schema:name New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem
    43 schema:pagination 342-367
    44 schema:productId N81b9bb601dc4476ebf9d44354d04a8ba
    45 Nf15a31c840974ba49baf3a107d202234
    46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045232696
    47 https://doi.org/10.1007/s00224-009-9165-y
    48 schema:sdDatePublished 2021-11-01T18:13
    49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    50 schema:sdPublisher N30cae75812d8498ea640f2ba5efa39e7
    51 schema:url https://doi.org/10.1007/s00224-009-9165-y
    52 sgo:license sg:explorer/license/
    53 sgo:sdDataset articles
    54 rdf:type schema:ScholarlyArticle
    55 N22ebd1db89c54d12a17ee8c57d18f506 rdf:first sg:person.013577077462.41
    56 rdf:rest N75db7989c4b044febd1485319c8a8f37
    57 N2894472c972c4d57a472ef344dde5451 rdf:first sg:person.013174232477.45
    58 rdf:rest N22ebd1db89c54d12a17ee8c57d18f506
    59 N30cae75812d8498ea640f2ba5efa39e7 schema:name Springer Nature - SN SciGraph project
    60 rdf:type schema:Organization
    61 N75db7989c4b044febd1485319c8a8f37 rdf:first sg:person.013545320167.55
    62 rdf:rest rdf:nil
    63 N81b9bb601dc4476ebf9d44354d04a8ba schema:name doi
    64 schema:value 10.1007/s00224-009-9165-y
    65 rdf:type schema:PropertyValue
    66 Nae9c686f983647d6b154a8fc4950ae59 schema:issueNumber 2
    67 rdf:type schema:PublicationIssue
    68 Ndd6d9fc1fd6443a889a758ea180d278d schema:volumeNumber 47
    69 rdf:type schema:PublicationVolume
    70 Nf15a31c840974ba49baf3a107d202234 schema:name dimensions_id
    71 schema:value pub.1045232696
    72 rdf:type schema:PropertyValue
    73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Information and Computing Sciences
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Artificial Intelligence and Image Processing
    78 rdf:type schema:DefinedTerm
    79 sg:journal.1052098 schema:issn 1432-4350
    80 1433-0490
    81 schema:name Theory of Computing Systems
    82 schema:publisher Springer Nature
    83 rdf:type schema:Periodical
    84 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
    85 schema:familyName Chang
    86 schema:givenName Maw-Shang
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
    88 rdf:type schema:Person
    89 sg:person.013545320167.55 schema:affiliation grid-institutes:grid.1957.a
    90 schema:familyName Rossmanith
    91 schema:givenName Peter
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013545320167.55
    93 rdf:type schema:Person
    94 sg:person.013577077462.41 schema:affiliation grid-institutes:grid.412047.4
    95 schema:familyName Lin
    96 schema:givenName Chuang-Chieh
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577077462.41
    98 rdf:type schema:Person
    99 sg:pub.10.1007/11557067_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049532580
    100 https://doi.org/10.1007/11557067_6
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/3-540-48481-7_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034130792
    103 https://doi.org/10.1007/3-540-48481-7_28
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/3-540-49477-4_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035836541
    106 https://doi.org/10.1007/3-540-49477-4_3
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/978-1-4612-0515-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050354225
    109 https://doi.org/10.1007/978-1-4612-0515-9
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/bf02618470 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015721561
    112 https://doi.org/10.1007/bf02618470
    113 rdf:type schema:CreativeWork
    114 grid-institutes:grid.1957.a schema:alternateName Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52056, Aachen, Germany
    115 schema:name Department of Computer Science, RWTH Aachen University, Ahornstr. 55, 52056, Aachen, Germany
    116 rdf:type schema:Organization
    117 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan
    118 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, 621, Ming-Hsiung, Chiayi, Taiwan
    119 rdf:type schema:Organization
     




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


    ...