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 N21c46e7d03b94d069ebbb099fad94d68
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 Ne7ebd5deabae4c31be5ba5b446d2fecb
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N54ae28dacf554041906db453fb44dc45
24 schema:name Fast Neighbor Joining
25 schema:pagination 1263-1274
26 schema:productId N4b2397b3909f4e6ebf130f66b6d0b2fa
27 N5cc243d64a8145a9831f343c9d41e48e
28 N9d8aede076c04ac1bdf28852623ec317
29 schema:publisher N9014ea2368a34750a80017d85e76c3e9
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 N58b91a5af450487682ad6ecd2ead331e
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 N04a35128712645e8ba695971e7336b33 rdf:first N52f74c83a2e0453e9211a66b590cc135
40 rdf:rest N191ad517483b462fbca8bd6aa21384a5
41 N191ad517483b462fbca8bd6aa21384a5 rdf:first N972be396fc774c4387e13b399521395c
42 rdf:rest N7e8126441fe242c9b074378c4ba7d9cc
43 N1dcdd42ef04c4d83a3ba608ca665fbab schema:familyName Italiano
44 schema:givenName Giuseppe F.
45 rdf:type schema:Person
46 N21c46e7d03b94d069ebbb099fad94d68 rdf:first sg:person.0674274675.62
47 rdf:rest N5248af59052546899395315c92d47d8f
48 N4b2397b3909f4e6ebf130f66b6d0b2fa schema:name dimensions_id
49 schema:value pub.1004861745
50 rdf:type schema:PropertyValue
51 N4df47f670e1d4f1b81e891420e16ad98 rdf:first N1dcdd42ef04c4d83a3ba608ca665fbab
52 rdf:rest N04a35128712645e8ba695971e7336b33
53 N5248af59052546899395315c92d47d8f rdf:first sg:person.0611475642.77
54 rdf:rest rdf:nil
55 N52f473a04f61477381041707cde1f99c schema:familyName Yung
56 schema:givenName Moti
57 rdf:type schema:Person
58 N52f74c83a2e0453e9211a66b590cc135 schema:familyName Monteiro
59 schema:givenName Luís
60 rdf:type schema:Person
61 N54ae28dacf554041906db453fb44dc45 schema:isbn 978-3-540-27580-0
62 978-3-540-31691-6
63 schema:name Automata, Languages and Programming
64 rdf:type schema:Book
65 N58b91a5af450487682ad6ecd2ead331e schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N5cc243d64a8145a9831f343c9d41e48e schema:name readcube_id
68 schema:value 172adfb3971138d93cac8abafed17707479f06ba32bed7340a918a2ffcce6b8e
69 rdf:type schema:PropertyValue
70 N7e8126441fe242c9b074378c4ba7d9cc rdf:first N52f473a04f61477381041707cde1f99c
71 rdf:rest rdf:nil
72 N7f48f07bae254007b4d70312df3d686f schema:familyName Caires
73 schema:givenName Luís
74 rdf:type schema:Person
75 N9014ea2368a34750a80017d85e76c3e9 schema:location Berlin, Heidelberg
76 schema:name Springer Berlin Heidelberg
77 rdf:type schema:Organisation
78 N972be396fc774c4387e13b399521395c schema:familyName Palamidessi
79 schema:givenName Catuscia
80 rdf:type schema:Person
81 N9d8aede076c04ac1bdf28852623ec317 schema:name doi
82 schema:value 10.1007/11523468_102
83 rdf:type schema:PropertyValue
84 Ne7ebd5deabae4c31be5ba5b446d2fecb rdf:first N7f48f07bae254007b4d70312df3d686f
85 rdf:rest N4df47f670e1d4f1b81e891420e16ad98
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)


...