Fast Error-Tolerant Quartet Phylogeny Algorithms View Full Text


Ontology type: schema:Chapter     


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

References to SciGraph publications

Book

TITLE

Combinatorial Pattern Matching

ISBN

978-3-642-21457-8
978-3-642-21458-5

Author Affiliations

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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://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": "University of Waterloo", 
          "id": "https://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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1093/oxfordjournals.molbev.a025664", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000153997"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/nar/30.1.276", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011151029"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-003-1065-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021604411", 
          "https://doi.org/10.1007/s00453-003-1065-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/molbev/msp077", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028540883"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/molbev/msp077", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028540883"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(99)00028-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030334849"
        ], 
        "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"
      }, 
      {
        "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"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49116-3_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036110859", 
          "https://doi.org/10.1007/3-540-49116-3_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49116-3_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036110859", 
          "https://doi.org/10.1007/3-540-49116-3_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-6-108", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037048502", 
          "https://doi.org/10.1186/1471-2105-6-108"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/100216.100230", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037097298"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1996.0035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045540105"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02008-7_32", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050043191", 
          "https://doi.org/10.1007/978-3-642-02008-7_32"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02008-7_32", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050043191", 
          "https://doi.org/10.1007/978-3-642-02008-7_32"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/oxfordjournals.molbev.a003881", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052052269"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/10665270252935467", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059204929"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/cmb.2007.0103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059245568"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcbb.2007.1008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061540533"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1998.743492", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095062891"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511581274", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098672101"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "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", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-21457-8", 
        "978-3-642-21458-5"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "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"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "26813d57e6c075c02f4d5697159797d6d63edfdf502f17270809e628a02a1851"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "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": "2019-04-16T08:58", 
    "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/0000000369_0000000369/records_68971_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-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.

133 TRIPLES      23 PREDICATES      44 URIs      20 LITERALS      8 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 N8a5d4d4777e041d5a7eebbc91263aa5e
4 schema:citation sg:pub.10.1007/3-540-48481-7_28
5 sg:pub.10.1007/3-540-49116-3_17
6 sg:pub.10.1007/978-3-642-02008-7_32
7 sg:pub.10.1007/s00453-003-1065-y
8 sg:pub.10.1186/1471-2105-6-108
9 https://doi.org/10.1006/jagm.1996.0035
10 https://doi.org/10.1016/s0304-3975(99)00028-6
11 https://doi.org/10.1017/cbo9780511581274
12 https://doi.org/10.1089/10665270252935467
13 https://doi.org/10.1089/cmb.2007.0103
14 https://doi.org/10.1093/molbev/msp077
15 https://doi.org/10.1093/nar/30.1.276
16 https://doi.org/10.1093/oxfordjournals.molbev.a003881
17 https://doi.org/10.1093/oxfordjournals.molbev.a025664
18 https://doi.org/10.1109/sfcs.1998.743492
19 https://doi.org/10.1109/tcbb.2007.1008
20 https://doi.org/10.1145/100216.100230
21 schema:datePublished 2011
22 schema:datePublishedReg 2011-01-01
23 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.
24 schema:editor Nae58f45cc8e1450597bcb91a7b66ba89
25 schema:genre chapter
26 schema:inLanguage en
27 schema:isAccessibleForFree false
28 schema:isPartOf N9a98e88624e44c02aa7060c3828d72b5
29 schema:name Fast Error-Tolerant Quartet Phylogeny Algorithms
30 schema:pagination 147-161
31 schema:productId N5f04c4e8181343c4b2ef966abe1e9e1c
32 Nab3d15cffead4c22857ef5be42e1194c
33 Ne063414496c64048b7d7d488dbb0d6cb
34 schema:publisher Ncf6385f9bd59408e993ad4d829463ab3
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008082437
36 https://doi.org/10.1007/978-3-642-21458-5_14
37 schema:sdDatePublished 2019-04-16T08:58
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N758ac4e0cc804d97b0b50d55cc89d642
40 schema:url https://link.springer.com/10.1007%2F978-3-642-21458-5_14
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N04c248a535b8465684da671e70d8596c schema:familyName Giancarlo
45 schema:givenName Raffaele
46 rdf:type schema:Person
47 N5f04c4e8181343c4b2ef966abe1e9e1c schema:name readcube_id
48 schema:value 26813d57e6c075c02f4d5697159797d6d63edfdf502f17270809e628a02a1851
49 rdf:type schema:PropertyValue
50 N758ac4e0cc804d97b0b50d55cc89d642 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N8a5d4d4777e041d5a7eebbc91263aa5e rdf:first sg:person.0642727740.54
53 rdf:rest Nf91b935b5f2544a88fb90afa9c36dd9d
54 N9a98e88624e44c02aa7060c3828d72b5 schema:isbn 978-3-642-21457-8
55 978-3-642-21458-5
56 schema:name Combinatorial Pattern Matching
57 rdf:type schema:Book
58 Na164fa5a859741d08be26d7d64943370 rdf:first Nafd0212d7b594df09bc4db864cb8c831
59 rdf:rest rdf:nil
60 Nab3d15cffead4c22857ef5be42e1194c schema:name doi
61 schema:value 10.1007/978-3-642-21458-5_14
62 rdf:type schema:PropertyValue
63 Nae58f45cc8e1450597bcb91a7b66ba89 rdf:first N04c248a535b8465684da671e70d8596c
64 rdf:rest Na164fa5a859741d08be26d7d64943370
65 Nafd0212d7b594df09bc4db864cb8c831 schema:familyName Manzini
66 schema:givenName Giovanni
67 rdf:type schema:Person
68 Ncf6385f9bd59408e993ad4d829463ab3 schema:location Berlin, Heidelberg
69 schema:name Springer Berlin Heidelberg
70 rdf:type schema:Organisation
71 Ne063414496c64048b7d7d488dbb0d6cb schema:name dimensions_id
72 schema:value pub.1008082437
73 rdf:type schema:PropertyValue
74 Nf91b935b5f2544a88fb90afa9c36dd9d rdf:first sg:person.01320220640.40
75 rdf:rest rdf:nil
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.01320220640.40 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
83 schema:familyName Truszkowski
84 schema:givenName Jakub
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01320220640.40
86 rdf:type schema:Person
87 sg:person.0642727740.54 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
88 schema:familyName Brown
89 schema:givenName Daniel G.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0642727740.54
91 rdf:type schema:Person
92 sg:pub.10.1007/3-540-48481-7_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034130792
93 https://doi.org/10.1007/3-540-48481-7_28
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/3-540-49116-3_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036110859
96 https://doi.org/10.1007/3-540-49116-3_17
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/978-3-642-02008-7_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050043191
99 https://doi.org/10.1007/978-3-642-02008-7_32
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/s00453-003-1065-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1021604411
102 https://doi.org/10.1007/s00453-003-1065-y
103 rdf:type schema:CreativeWork
104 sg:pub.10.1186/1471-2105-6-108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037048502
105 https://doi.org/10.1186/1471-2105-6-108
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1006/jagm.1996.0035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045540105
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/s0304-3975(99)00028-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030334849
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1017/cbo9780511581274 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098672101
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1089/10665270252935467 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059204929
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1089/cmb.2007.0103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059245568
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1093/molbev/msp077 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028540883
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1093/nar/30.1.276 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011151029
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1093/oxfordjournals.molbev.a003881 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052052269
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1093/oxfordjournals.molbev.a025664 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000153997
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1109/sfcs.1998.743492 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095062891
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1109/tcbb.2007.1008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061540533
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1145/100216.100230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037097298
130 rdf:type schema:CreativeWork
131 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
132 schema:name David R. Cheriton School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, ON, Canada
133 rdf:type schema:Organization
 




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


...