Bioinformatics.org Membership (42988+) Basic Free! Professional Group hosting  Wiki Franklin Award Sponsorships

 Research All information groups Online databases Online analysis tools Online education tools More tools

 Development All software groups FTP repository SVN & CVS repositories Mailing lists

 Forums News & Commentary Submit Archives Subscribe Jobs Forum(Career Center) Submit Archives Subscribe

 News & Commentary - Message forums
Software: Accelerating the neighbor-joining algorithm using the adaptive bucket data structure
Submitted by Dr. Leonid Zaslavsky; posted on Tuesday, May 27, 2008

# ARTICLE

Leonid Zaslavsky and Tatiana A. Tatusova. 2008. ``Accelerating the neighbor-joining algorithm using the adaptive bucket data structure''. Lecture Notes in Computer Science 4983:122-133. http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pubmed&pubmedid=18478099

# ABSTRACT

The complexity of the neighbor joining method is determined by the complexity of the search for an optimal pair ("neighbors to join") performed globally at each iteration. Accelerating the neighbor-joining method requires performing a smarter search for an optimal pair of neighbors, avoiding re-evaluation of all possible pairs of points at each iteration. We developed an acceleration technique for the neighbor-joining method that significantly decreases complexity for important applications without any change in the neighbor-joining method. This technique utilizes the bucket data structure. The pairs of nodes are arranged in buckets according to values of the goal function delta(ij) = u(i) + u(j) - d(ij). Buckets are adaptively re-arranged after each neighbor-joining step. While the pairs of nodes in the top bucket are re-evaluated at every iteration, pairs in lower buckets are accessed more rarely, when the algorithm determines that the elements of the bucket need to be re-evaluated based on new values of delta(ij). As a result, only a small portion of candidate pairs of nodes is examined at each iteration. The algorithm is cache efficient, since the bucket data structures are able to exploit locality and adjust to cache properties.

Expanded view | Monitor forum | Save place

You have to be logged in to post a reply.