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

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 N4ebf0819c6e146ecb0365565a6be9a91
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 Ndfa5e8d1d5e84a7c8d0b4fdeb44ed391
25 schema:genre chapter
26 schema:inLanguage en
27 schema:isAccessibleForFree false
28 schema:isPartOf N6df96fcef88d46edbe8dc03d2384824e
29 schema:name Fast Error-Tolerant Quartet Phylogeny Algorithms
30 schema:pagination 147-161
31 schema:productId N24ff9538207e46dc81ff4ea69e6dbfe6
32 Na159c53cade748da80352afef71a0c74
33 Nb908558a4e9b4b5481607bf855ad4f6a
34 schema:publisher Na063486b58784bf0981ea3eca7952e6e
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 N31988259b0744a58996c4557ea8fb424
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 N110ac5b089d14056835d4f7fd8f39e8f schema:familyName Giancarlo
45 schema:givenName Raffaele
46 rdf:type schema:Person
47 N24ff9538207e46dc81ff4ea69e6dbfe6 schema:name doi
48 schema:value 10.1007/978-3-642-21458-5_14
49 rdf:type schema:PropertyValue
50 N31988259b0744a58996c4557ea8fb424 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N4ebf0819c6e146ecb0365565a6be9a91 rdf:first sg:person.0642727740.54
53 rdf:rest Nb24ecf9a3c614ab19964a6ae8fd7fc5f
54 N54a7cd617ae84d33948749e3a586828a rdf:first Nb4a473482899400eb3ec07c96d6fad7e
55 rdf:rest rdf:nil
56 N6df96fcef88d46edbe8dc03d2384824e schema:isbn 978-3-642-21457-8
57 978-3-642-21458-5
58 schema:name Combinatorial Pattern Matching
59 rdf:type schema:Book
60 Na063486b58784bf0981ea3eca7952e6e schema:location Berlin, Heidelberg
61 schema:name Springer Berlin Heidelberg
62 rdf:type schema:Organisation
63 Na159c53cade748da80352afef71a0c74 schema:name dimensions_id
64 schema:value pub.1008082437
65 rdf:type schema:PropertyValue
66 Nb24ecf9a3c614ab19964a6ae8fd7fc5f rdf:first sg:person.01320220640.40
67 rdf:rest rdf:nil
68 Nb4a473482899400eb3ec07c96d6fad7e schema:familyName Manzini
69 schema:givenName Giovanni
70 rdf:type schema:Person
71 Nb908558a4e9b4b5481607bf855ad4f6a schema:name readcube_id
72 schema:value 26813d57e6c075c02f4d5697159797d6d63edfdf502f17270809e628a02a1851
73 rdf:type schema:PropertyValue
74 Ndfa5e8d1d5e84a7c8d0b4fdeb44ed391 rdf:first N110ac5b089d14056835d4f7fd8f39e8f
75 rdf:rest N54a7cd617ae84d33948749e3a586828a
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)


...