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 Naffbb030f8894fba96acaebfe54f7985
    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 N4f976df98bed47b398d070c571d1023c
    12 N6e4b6a1541e04a8bb1c8eeb9ca2514f2
    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 N527a7d76ad534c70915d5662a07618ca
    17 N92e4da053e804947a2c6002e97f5e879
    18 Nba2c3633e8c24fdb8a295f0056004989
    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 N572c0418706f4114a3d5c9ed62e8e9d1
    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 N4f976df98bed47b398d070c571d1023c schema:issueNumber 2
    29 rdf:type schema:PublicationIssue
    30 N527a7d76ad534c70915d5662a07618ca schema:name dimensions_id
    31 schema:value pub.1021604411
    32 rdf:type schema:PropertyValue
    33 N572c0418706f4114a3d5c9ed62e8e9d1 schema:name Springer Nature - SN SciGraph project
    34 rdf:type schema:Organization
    35 N5a0d4f3112e94aa89564c158d43a2de2 rdf:first sg:person.013654773317.40
    36 rdf:rest rdf:nil
    37 N6e4b6a1541e04a8bb1c8eeb9ca2514f2 schema:volumeNumber 38
    38 rdf:type schema:PublicationVolume
    39 N92e4da053e804947a2c6002e97f5e879 schema:name readcube_id
    40 schema:value 66ef3f80fd62fad12368f703e72f5eb352d1008767c2119111459af0c4f763c5
    41 rdf:type schema:PropertyValue
    42 Naffbb030f8894fba96acaebfe54f7985 rdf:first sg:person.014743243317.57
    43 rdf:rest Nb18b669f71f341a39bf9ed01763a2d91
    44 Nb18b669f71f341a39bf9ed01763a2d91 rdf:first sg:person.011575705143.79
    45 rdf:rest N5a0d4f3112e94aa89564c158d43a2de2
    46 Nba2c3633e8c24fdb8a295f0056004989 schema:name doi
    47 schema:value 10.1007/s00453-003-1065-y
    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)


    ...