Fast Error-Tolerant Quartet Phylogeny Algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Daniel G. Brown , Jakub Truszkowski

ABSTRACT

We present a quartet-based phylogeny algorithm that returns the correct topology for n taxa in O(n logn) time with high probability, assuming each quartet is inconsistent with the true tree topology with constant probability, independent of other quartets. Our incremental algorithm relies upon a search tree structure for the phylogeny that is balanced, with high probability, no matter the true topology. In experiments, our prototype was as fast as the fastest heuristics, but because real data do not typically satisfy our probabilistic assumptions, its overall performance is not as good as our theoretical results predict. More... »

PAGES

147-161

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-21458-5_14

DOI

http://dx.doi.org/10.1007/978-3-642-21458-5_14

DIMENSIONS

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


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": "David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brown", 
        "givenName": "Daniel G.", 
        "id": "sg:person.0642727740.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Truszkowski", 
        "givenName": "Jakub", 
        "id": "sg:person.01320220640.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01320220640.40"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We present a quartet-based phylogeny algorithm that returns the correct topology for n taxa in O(n logn) time with high probability, assuming each quartet is inconsistent with the true tree topology with constant probability, independent of other quartets. Our incremental algorithm relies upon a search tree structure for the phylogeny that is balanced, with high probability, no matter the true topology. In experiments, our prototype was as fast as the fastest heuristics, but because real data do not typically satisfy our probabilistic assumptions, its overall performance is not as good as our theoretical results predict.", 
    "editor": [
      {
        "familyName": "Giancarlo", 
        "givenName": "Raffaele", 
        "type": "Person"
      }, 
      {
        "familyName": "Manzini", 
        "givenName": "Giovanni", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-21458-5_14", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-21457-8", 
        "978-3-642-21458-5"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "keywords": [
      "search tree structure", 
      "phylogeny algorithms", 
      "fast heuristic", 
      "algorithm relies", 
      "tree structure", 
      "real data", 
      "probabilistic assumptions", 
      "n taxa", 
      "theoretical results", 
      "true topology", 
      "algorithm", 
      "overall performance", 
      "tree topology", 
      "constant probability", 
      "topology", 
      "high probability", 
      "correct topology", 
      "heuristics", 
      "probability", 
      "prototype", 
      "performance", 
      "relies", 
      "assumption", 
      "data", 
      "quartet", 
      "experiments", 
      "time", 
      "structure", 
      "results", 
      "phylogeny", 
      "taxa"
    ], 
    "name": "Fast Error-Tolerant Quartet Phylogeny Algorithms", 
    "pagination": "147-161", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008082437"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-21458-5_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-21458-5_14", 
      "https://app.dimensions.ai/details/publication/pub.1008082437"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_350.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-21458-5_14"
  }
]
 

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/978-3-642-21458-5_14'

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/978-3-642-21458-5_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21458-5_14'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21458-5_14'


 

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

102 TRIPLES      22 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-21458-5_14 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3f416682e70a4f45b491f585682b0445
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We present a quartet-based phylogeny algorithm that returns the correct topology for n taxa in O(n logn) time with high probability, assuming each quartet is inconsistent with the true tree topology with constant probability, independent of other quartets. Our incremental algorithm relies upon a search tree structure for the phylogeny that is balanced, with high probability, no matter the true topology. In experiments, our prototype was as fast as the fastest heuristics, but because real data do not typically satisfy our probabilistic assumptions, its overall performance is not as good as our theoretical results predict.
7 schema:editor N512306a68d3c4afeac06ea3ca17e9ba5
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N92b46cdab9b2483089cbbf5d2b136b02
11 schema:keywords algorithm
12 algorithm relies
13 assumption
14 constant probability
15 correct topology
16 data
17 experiments
18 fast heuristic
19 heuristics
20 high probability
21 n taxa
22 overall performance
23 performance
24 phylogeny
25 phylogeny algorithms
26 probabilistic assumptions
27 probability
28 prototype
29 quartet
30 real data
31 relies
32 results
33 search tree structure
34 structure
35 taxa
36 theoretical results
37 time
38 topology
39 tree structure
40 tree topology
41 true topology
42 schema:name Fast Error-Tolerant Quartet Phylogeny Algorithms
43 schema:pagination 147-161
44 schema:productId Nbe2fc0029d8345ba95726e0e1909b119
45 Ne7a0651252c44b63b3fe29ba57dffaec
46 schema:publisher N2abc59195f9547e699cac0ef53e43484
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008082437
48 https://doi.org/10.1007/978-3-642-21458-5_14
49 schema:sdDatePublished 2022-12-01T06:52
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N61c781fd8e684e6d8350d2780b290073
52 schema:url https://doi.org/10.1007/978-3-642-21458-5_14
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N2abc59195f9547e699cac0ef53e43484 schema:name Springer Nature
57 rdf:type schema:Organisation
58 N3f416682e70a4f45b491f585682b0445 rdf:first sg:person.0642727740.54
59 rdf:rest N5057c0fe0f8c4f15b2a5524aa661b3a1
60 N5057c0fe0f8c4f15b2a5524aa661b3a1 rdf:first sg:person.01320220640.40
61 rdf:rest rdf:nil
62 N512306a68d3c4afeac06ea3ca17e9ba5 rdf:first Ndd89faee80674e7ab1e35579a68bf76a
63 rdf:rest Ned2e1629939148a9903316b9b56b0c00
64 N546cc22ca95a402eabd5d3d19b549569 schema:familyName Manzini
65 schema:givenName Giovanni
66 rdf:type schema:Person
67 N61c781fd8e684e6d8350d2780b290073 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N92b46cdab9b2483089cbbf5d2b136b02 schema:isbn 978-3-642-21457-8
70 978-3-642-21458-5
71 schema:name Combinatorial Pattern Matching
72 rdf:type schema:Book
73 Nbe2fc0029d8345ba95726e0e1909b119 schema:name doi
74 schema:value 10.1007/978-3-642-21458-5_14
75 rdf:type schema:PropertyValue
76 Ndd89faee80674e7ab1e35579a68bf76a schema:familyName Giancarlo
77 schema:givenName Raffaele
78 rdf:type schema:Person
79 Ne7a0651252c44b63b3fe29ba57dffaec schema:name dimensions_id
80 schema:value pub.1008082437
81 rdf:type schema:PropertyValue
82 Ned2e1629939148a9903316b9b56b0c00 rdf:first N546cc22ca95a402eabd5d3d19b549569
83 rdf:rest rdf:nil
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
88 schema:name Computation Theory and Mathematics
89 rdf:type schema:DefinedTerm
90 sg:person.01320220640.40 schema:affiliation grid-institutes:grid.46078.3d
91 schema:familyName Truszkowski
92 schema:givenName Jakub
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01320220640.40
94 rdf:type schema:Person
95 sg:person.0642727740.54 schema:affiliation grid-institutes:grid.46078.3d
96 schema:familyName Brown
97 schema:givenName Daniel G.
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
99 rdf:type schema:Person
100 grid-institutes:grid.46078.3d schema:alternateName David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
101 schema:name David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
102 rdf:type schema:Organization
 




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


...