Computing the Quartet Distance between Evolutionary Trees in Time O(n log n) View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2004-02

AUTHORS

Gerth Stølting Brodal, Rolf Fagerberg, Christian N.S. Pedersen

ABSTRACT

Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris, and Meacham. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species, where all internal nodes have degree three, in time O(n log n. The previous best algorithm for the problem uses time O(n2). More... »

PAGES

377-395

References to SciGraph publications

  • 2002-01-18. Efficient Merging, Construction, and Maintenance of Evolutionary Trees in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Journal

    TITLE

    Algorithmica

    ISSUE

    2

    VOLUME

    38

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-003-1065-y

    DOI

    http://dx.doi.org/10.1007/s00453-003-1065-y

    DIMENSIONS

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


    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/0604", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Genetics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Biological Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Aarhus University", 
              "id": "https://www.grid.ac/institutes/grid.7048.b", 
              "name": [
                "Department of Computer Science, University\n    of Aarhus, Ny Munkegade, DK-8000 \u00c5rhus C, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Brodal", 
            "givenName": "Gerth St\u00f8lting", 
            "id": "sg:person.014743243317.57", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014743243317.57"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Aarhus University", 
              "id": "https://www.grid.ac/institutes/grid.7048.b", 
              "name": [
                "Department of Computer Science, University\n    of Aarhus, Ny Munkegade, DK-8000 \u00c5rhus C, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fagerberg", 
            "givenName": "Rolf", 
            "id": "sg:person.011575705143.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011575705143.79"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Aarhus University", 
              "id": "https://www.grid.ac/institutes/grid.7048.b", 
              "name": [
                "Department of Computer Science, University\n    of Aarhus, Ny Munkegade, DK-8000 \u00c5rhus C, Denmark"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pedersen", 
            "givenName": "Christian N.S.", 
            "id": "sg:person.013654773317.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013654773317.40"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-48523-6_51", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024049527", 
              "https://doi.org/10.1007/3-540-48523-6_51"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48523-6_51", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024049527", 
              "https://doi.org/10.1007/3-540-48523-6_51"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004-02", 
        "datePublishedReg": "2004-02-01", 
        "description": "Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris, and Meacham. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species, where all internal nodes have degree three, in time O(n log n. The previous best algorithm for the problem uses time O(n2).", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00453-003-1065-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "38"
          }
        ], 
        "name": "Computing the Quartet Distance between Evolutionary Trees in Time O(n log n)", 
        "pagination": "377-395", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "66ef3f80fd62fad12368f703e72f5eb352d1008767c2119111459af0c4f763c5"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-003-1065-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1021604411"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-003-1065-y", 
          "https://app.dimensions.ai/details/publication/pub.1021604411"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T19:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8678_00000512.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00453-003-1065-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/s00453-003-1065-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/s00453-003-1065-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1065-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-003-1065-y'


     

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

    79 TRIPLES      21 PREDICATES      28 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-003-1065-y schema:about anzsrc-for:06
    2 anzsrc-for:0604
    3 schema:author N901bfc4aa00e40e9826b8d4b4593ef80
    4 schema:citation sg:pub.10.1007/3-540-48523-6_51
    5 schema:datePublished 2004-02
    6 schema:datePublishedReg 2004-02-01
    7 schema:description Evolutionary trees describing the relationship for a set of species are central in evolutionary biology, and quantifying differences between evolutionary trees is therefore an important task. The quartet distance is a distance measure between trees previously proposed by Estabrook, McMorris, and Meacham. The quartet distance between two unrooted evolutionary trees is the number of quartet topology differences between the two trees, where a quartet topology is the topological subtree induced by four species. In this paper we present an algorithm for computing the quartet distance between two unrooted evolutionary trees of n species, where all internal nodes have degree three, in time O(n log n. The previous best algorithm for the problem uses time O(n2).
    8 schema:genre research_article
    9 schema:inLanguage en
    10 schema:isAccessibleForFree true
    11 schema:isPartOf N0687927b26a94d379af015adba9b0269
    12 Na1cf480802da4902890af6473d1081cf
    13 sg:journal.1047644
    14 schema:name Computing the Quartet Distance between Evolutionary Trees in Time O(n log n)
    15 schema:pagination 377-395
    16 schema:productId N619a31e40c864d8db86dda47ee5319ad
    17 N96f592480ddb4c799f4c41acecfebb17
    18 Nef8c4cca20694b5dbcef1d904653ea54
    19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021604411
    20 https://doi.org/10.1007/s00453-003-1065-y
    21 schema:sdDatePublished 2019-04-10T19:08
    22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    23 schema:sdPublisher Nbf6897ddbf224c598e45eb7b0d5d8fa6
    24 schema:url http://link.springer.com/10.1007%2Fs00453-003-1065-y
    25 sgo:license sg:explorer/license/
    26 sgo:sdDataset articles
    27 rdf:type schema:ScholarlyArticle
    28 N0687927b26a94d379af015adba9b0269 schema:volumeNumber 38
    29 rdf:type schema:PublicationVolume
    30 N0eb307aa130e45df9e6cd969765c3907 rdf:first sg:person.013654773317.40
    31 rdf:rest rdf:nil
    32 N48a832fc2b29458b86f5276eb0a450f0 rdf:first sg:person.011575705143.79
    33 rdf:rest N0eb307aa130e45df9e6cd969765c3907
    34 N619a31e40c864d8db86dda47ee5319ad schema:name doi
    35 schema:value 10.1007/s00453-003-1065-y
    36 rdf:type schema:PropertyValue
    37 N901bfc4aa00e40e9826b8d4b4593ef80 rdf:first sg:person.014743243317.57
    38 rdf:rest N48a832fc2b29458b86f5276eb0a450f0
    39 N96f592480ddb4c799f4c41acecfebb17 schema:name dimensions_id
    40 schema:value pub.1021604411
    41 rdf:type schema:PropertyValue
    42 Na1cf480802da4902890af6473d1081cf schema:issueNumber 2
    43 rdf:type schema:PublicationIssue
    44 Nbf6897ddbf224c598e45eb7b0d5d8fa6 schema:name Springer Nature - SN SciGraph project
    45 rdf:type schema:Organization
    46 Nef8c4cca20694b5dbcef1d904653ea54 schema:name readcube_id
    47 schema:value 66ef3f80fd62fad12368f703e72f5eb352d1008767c2119111459af0c4f763c5
    48 rdf:type schema:PropertyValue
    49 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
    50 schema:name Biological Sciences
    51 rdf:type schema:DefinedTerm
    52 anzsrc-for:0604 schema:inDefinedTermSet anzsrc-for:
    53 schema:name Genetics
    54 rdf:type schema:DefinedTerm
    55 sg:journal.1047644 schema:issn 0178-4617
    56 1432-0541
    57 schema:name Algorithmica
    58 rdf:type schema:Periodical
    59 sg:person.011575705143.79 schema:affiliation https://www.grid.ac/institutes/grid.7048.b
    60 schema:familyName Fagerberg
    61 schema:givenName Rolf
    62 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011575705143.79
    63 rdf:type schema:Person
    64 sg:person.013654773317.40 schema:affiliation https://www.grid.ac/institutes/grid.7048.b
    65 schema:familyName Pedersen
    66 schema:givenName Christian N.S.
    67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013654773317.40
    68 rdf:type schema:Person
    69 sg:person.014743243317.57 schema:affiliation https://www.grid.ac/institutes/grid.7048.b
    70 schema:familyName Brodal
    71 schema:givenName Gerth Stølting
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014743243317.57
    73 rdf:type schema:Person
    74 sg:pub.10.1007/3-540-48523-6_51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024049527
    75 https://doi.org/10.1007/3-540-48523-6_51
    76 rdf:type schema:CreativeWork
    77 https://www.grid.ac/institutes/grid.7048.b schema:alternateName Aarhus University
    78 schema:name Department of Computer Science, University of Aarhus, Ny Munkegade, DK-8000 Århus C, Denmark
    79 rdf:type schema:Organization
     




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


    ...