Fast Neighbor Joining View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Isaac Elias , Jens Lagergren

ABSTRACT

Reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. Neighbor Joining (NJ) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. It takes the distances between n taxa and produces in Θ(n3) time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. In addition to performing well in practice, the NJ algorithm has optimal reconstruction radius. The contribution of this paper is twofold: (1) we present an algorithm called Fast Neighbor Joining (FNJ) with optimal reconstruction radius and optimal run time complexity O(n2) and (2) we present a greatly simplified proof for the correctness of NJ. Initial experiments show that FNJ in practice has almost the same accuracy as NJ, indicating that the property of optimal reconstruction radius has great importance to their good performance. Moreover, we show how improved running time can be achieved for computing the so-called correction formulas. More... »

PAGES

1263-1274

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-27580-0
978-3-540-31691-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11523468_102

DOI

http://dx.doi.org/10.1007/11523468_102

DIMENSIONS

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


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/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "Dept. of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Elias", 
        "givenName": "Isaac", 
        "id": "sg:person.0674274675.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674274675.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "Dept. of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lagergren", 
        "givenName": "Jens", 
        "id": "sg:person.0611475642.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0611475642.77"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1002/(sici)1098-2418(199903)14:2<153::aid-rsa3>3.0.co;2-r", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013265373"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/28395.28396", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018137247"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01731581", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023239976", 
          "https://doi.org/10.1007/bf01731581"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01731581", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023239976", 
          "https://doi.org/10.1007/bf01731581"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01731581", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023239976", 
          "https://doi.org/10.1007/bf01731581"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00008277", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030470236", 
          "https://doi.org/10.1007/pl00008277"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/bioinformatics/13.3.235", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044605581"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(02)00005-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047974605"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(02)00005-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047974605"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/106652702761034136", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059204960"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1089/106652799318337", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059205065"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539795296334", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880082"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/oxfordjournals.molbev.a040454", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1079752303"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/9789812799623_0020", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1096079230"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/dimacs/037", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1097022570"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. Neighbor Joining (NJ) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. It takes the distances between n taxa and produces in \u0398(n3) time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. In addition to performing well in practice, the NJ algorithm has optimal reconstruction radius. The contribution of this paper is twofold: (1) we present an algorithm called Fast Neighbor Joining (FNJ) with optimal reconstruction radius and optimal run time complexity O(n2) and (2) we present a greatly simplified proof for the correctness of NJ. Initial experiments show that FNJ in practice has almost the same accuracy as NJ, indicating that the property of optimal reconstruction radius has great importance to their good performance. Moreover, we show how improved running time can be achieved for computing the so-called correction formulas.", 
    "editor": [
      {
        "familyName": "Caires", 
        "givenName": "Lu\u00eds", 
        "type": "Person"
      }, 
      {
        "familyName": "Italiano", 
        "givenName": "Giuseppe F.", 
        "type": "Person"
      }, 
      {
        "familyName": "Monteiro", 
        "givenName": "Lu\u00eds", 
        "type": "Person"
      }, 
      {
        "familyName": "Palamidessi", 
        "givenName": "Catuscia", 
        "type": "Person"
      }, 
      {
        "familyName": "Yung", 
        "givenName": "Moti", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11523468_102", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-27580-0", 
        "978-3-540-31691-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "Fast Neighbor Joining", 
    "pagination": "1263-1274", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004861745"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11523468_102"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "172adfb3971138d93cac8abafed17707479f06ba32bed7340a918a2ffcce6b8e"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11523468_102", 
      "https://app.dimensions.ai/details/publication/pub.1004861745"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:04", 
    "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/0000000359_0000000359/records_29215_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11523468_102"
  }
]
 

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/11523468_102'

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/11523468_102'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11523468_102'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11523468_102'


 

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

130 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11523468_102 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N57cbf5fb2c424e1c9406728f147eca75
4 schema:citation sg:pub.10.1007/bf01731581
5 sg:pub.10.1007/pl00008277
6 https://doi.org/10.1002/(sici)1098-2418(199903)14:2<153::aid-rsa3>3.0.co;2-r
7 https://doi.org/10.1016/s0022-0000(02)00005-3
8 https://doi.org/10.1089/106652702761034136
9 https://doi.org/10.1089/106652799318337
10 https://doi.org/10.1090/dimacs/037
11 https://doi.org/10.1093/bioinformatics/13.3.235
12 https://doi.org/10.1093/oxfordjournals.molbev.a040454
13 https://doi.org/10.1137/s0097539795296334
14 https://doi.org/10.1142/9789812799623_0020
15 https://doi.org/10.1145/28395.28396
16 schema:datePublished 2005
17 schema:datePublishedReg 2005-01-01
18 schema:description Reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. Neighbor Joining (NJ) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. It takes the distances between n taxa and produces in Θ(n3) time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. In addition to performing well in practice, the NJ algorithm has optimal reconstruction radius. The contribution of this paper is twofold: (1) we present an algorithm called Fast Neighbor Joining (FNJ) with optimal reconstruction radius and optimal run time complexity O(n2) and (2) we present a greatly simplified proof for the correctness of NJ. Initial experiments show that FNJ in practice has almost the same accuracy as NJ, indicating that the property of optimal reconstruction radius has great importance to their good performance. Moreover, we show how improved running time can be achieved for computing the so-called correction formulas.
19 schema:editor Nc8eed5617e40440a8d2d974c80571476
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N98fc5498407f44f6a7efc3eecb1058e8
24 schema:name Fast Neighbor Joining
25 schema:pagination 1263-1274
26 schema:productId N2200bcfe2c9c43aa8b216fe616701cad
27 N3ffae0b761a44b46b0625b56cf7035de
28 N9f2feac2b3bd4cc3b8c368ec911180c0
29 schema:publisher Nf27e86c210df40d0a6605aeb5bf6f0f4
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004861745
31 https://doi.org/10.1007/11523468_102
32 schema:sdDatePublished 2019-04-16T08:04
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Nc3023af1808c4df19aff05dec8d75c0e
35 schema:url https://link.springer.com/10.1007%2F11523468_102
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N0df21366c65f4a2fb943b1672183d603 rdf:first sg:person.0611475642.77
40 rdf:rest rdf:nil
41 N2200bcfe2c9c43aa8b216fe616701cad schema:name doi
42 schema:value 10.1007/11523468_102
43 rdf:type schema:PropertyValue
44 N38a80b677e3a4b91aecd57e527f9a68f schema:familyName Palamidessi
45 schema:givenName Catuscia
46 rdf:type schema:Person
47 N3ffae0b761a44b46b0625b56cf7035de schema:name dimensions_id
48 schema:value pub.1004861745
49 rdf:type schema:PropertyValue
50 N57cbf5fb2c424e1c9406728f147eca75 rdf:first sg:person.0674274675.62
51 rdf:rest N0df21366c65f4a2fb943b1672183d603
52 N6542fb99f40e47778f74a33870dc661d schema:familyName Caires
53 schema:givenName Luís
54 rdf:type schema:Person
55 N675323685f7940ba995e6d68b2abeec0 rdf:first N8c56bb9087a14ab69d2508be5dc9bef9
56 rdf:rest Nfa916cfe01fb4940ace8735a1521a79b
57 N70bfa5291623419997ae307d20f21759 rdf:first N92dbaeddd4cc494596ebca5a9b9c2b1a
58 rdf:rest rdf:nil
59 N8c56bb9087a14ab69d2508be5dc9bef9 schema:familyName Italiano
60 schema:givenName Giuseppe F.
61 rdf:type schema:Person
62 N92dbaeddd4cc494596ebca5a9b9c2b1a schema:familyName Yung
63 schema:givenName Moti
64 rdf:type schema:Person
65 N98fc5498407f44f6a7efc3eecb1058e8 schema:isbn 978-3-540-27580-0
66 978-3-540-31691-6
67 schema:name Automata, Languages and Programming
68 rdf:type schema:Book
69 N9f2feac2b3bd4cc3b8c368ec911180c0 schema:name readcube_id
70 schema:value 172adfb3971138d93cac8abafed17707479f06ba32bed7340a918a2ffcce6b8e
71 rdf:type schema:PropertyValue
72 Nc3023af1808c4df19aff05dec8d75c0e schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Nc8eed5617e40440a8d2d974c80571476 rdf:first N6542fb99f40e47778f74a33870dc661d
75 rdf:rest N675323685f7940ba995e6d68b2abeec0
76 Ndaeb39e6270f4126aa937fb0322b7bd7 schema:familyName Monteiro
77 schema:givenName Luís
78 rdf:type schema:Person
79 Nf27e86c210df40d0a6605aeb5bf6f0f4 schema:location Berlin, Heidelberg
80 schema:name Springer Berlin Heidelberg
81 rdf:type schema:Organisation
82 Nfa916cfe01fb4940ace8735a1521a79b rdf:first Ndaeb39e6270f4126aa937fb0322b7bd7
83 rdf:rest Nfb322d6cd4904b01817c6426dce3e3fb
84 Nfb322d6cd4904b01817c6426dce3e3fb rdf:first N38a80b677e3a4b91aecd57e527f9a68f
85 rdf:rest N70bfa5291623419997ae307d20f21759
86 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
87 schema:name Mathematical Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
90 schema:name Applied Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.0611475642.77 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
93 schema:familyName Lagergren
94 schema:givenName Jens
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0611475642.77
96 rdf:type schema:Person
97 sg:person.0674274675.62 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
98 schema:familyName Elias
99 schema:givenName Isaac
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674274675.62
101 rdf:type schema:Person
102 sg:pub.10.1007/bf01731581 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023239976
103 https://doi.org/10.1007/bf01731581
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/pl00008277 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030470236
106 https://doi.org/10.1007/pl00008277
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1002/(sici)1098-2418(199903)14:2<153::aid-rsa3>3.0.co;2-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1013265373
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/s0022-0000(02)00005-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047974605
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1089/106652702761034136 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059204960
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1089/106652799318337 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059205065
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1090/dimacs/037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022570
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1093/bioinformatics/13.3.235 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044605581
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1093/oxfordjournals.molbev.a040454 schema:sameAs https://app.dimensions.ai/details/publication/pub.1079752303
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/s0097539795296334 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880082
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1142/9789812799623_0020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096079230
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/28395.28396 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018137247
127 rdf:type schema:CreativeWork
128 https://www.grid.ac/institutes/grid.5037.1 schema:alternateName Royal Institute of Technology
129 schema:name Dept. of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, Sweden
130 rdf:type schema:Organization
 




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


...