Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fast neighbor joining
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2005 (English)In: AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS / [ed] Caires, L; Italiano, GE; Monteiro, L; Palamidessi, C; Yung, M, 2005, Vol. 3580, 1263-1274 p.Conference paper, Published paper (Refereed)
Abstract [en]

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 Theta(n(3)) 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(n(2)) 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.

Place, publisher, year, edition, pages
2005. Vol. 3580, 1263-1274 p.
Series
LECTURE NOTES IN COMPUTER SCIENCE, ISSN 0302-9743 ; 3580
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-42730ISI: 000230880500102Scopus ID: 2-s2.0-26444590958ISBN: 3-540-27580-0 (print)OAI: oai:DiVA.org:kth-42730DiVA: diva2:448078
Conference
32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) Location: Lisbon, PORTUGAL Date: JUL 11-15, 2005
Note
QC 20111014Available from: 2011-10-14 Created: 2011-10-12 Last updated: 2011-10-14Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Elias, IsaacLagergren, Jens
By organisation
Numerical Analysis and Computer Science, NADA
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf