Scholars Central

Research articlePublished 19 Jul 2012

FastJoin, an improved neighbor-joining algorithm

Authors: J. Wang, M.-Z. Guo, L.L. Xing

Genetics and Molecular Research

Volume 11 · Issue 3 · Pages 1909–1922

Ask about this article

Abstract

Select any words in the title or abstract, or press this and choose a sentence.

Reconstructing the evolutionary history of a set of species is an elementary problem in biology, and methods for solving this problem are evaluated based on two characteristics: accuracy and efficiency. Neighbor-joining reconstructs phylogenetic trees by iteratively picking a pair of nodes to merge as a new node until only one node remains; due to its good accuracy and speed, it has been embraced by the phylogeny research community. With the advent of large amounts of data, improved fast and precise methods for reconstructing evolutionary trees have become necessary. We improved the neighbor-joining algorithm by iteratively picking two pairs of nodes and merging as two new nodes, until only one node remains. We found that another pair of true neighbors could be chosen to merge as a new node besides the pair of true neighbors chosen by the criterion of the neighbor-joining method, in each iteration of the clustering procedure for the purely additive tree. These new neighbors will be selected by another iteration of the neighbor-joining method, so that they provide an improved neighbor-joining algorithm, by iteratively picking two pairs of nodes to merge as two new nodes until only one node remains, constructing the same phylogenetic tree as the neighbor-joining algorithm for the same input data. By combining the improved neighbor-joining algorithm with styles upper bound computation optimization of RapidNJ and external storage of ERapidNJ methods, a new method of reconstructing phylogenetic trees, FastJoin, was proposed. Experiments with sets of data showed that this new neighbor-joining algorithm yields a significant speed-up compared to classic neighbor-joining, showing empirically that FastJoin is superior to almost all other neighbor-joining implementations.

Ask about this article

Answers come only from this article's title, abstract and keywords, each sentence pointing to where it comes from. Your question is sent to OpenAI to write the answer. Scholars Central does not store it.

Try:

Similar by topic

More from this journal

The newest in Genetics and Molecular Research.

All its articles

Conferences in this field

Upcoming conferences in this field.

Follow

New articles from what you follow go into your email digest, once you agree to alert emails.

  • JournalGenetics and Molecular Research
  • SubjectGenetics & Molecular Biology
  • BylineArticles whose byline prints “J. Wang”
  • BylineArticles whose byline prints “M.-Z. Guo”
  • BylineArticles whose byline prints “L.L. Xing”

For authors and organisers

Publish, present and keep up with your field

Find the right journal for your paper and submit your manuscript.

Photo: Pexels