[University of Birmingham]
Not logged in
  • Log in
    Membership (42988+) Group hosting [?] Wiki
    Franklin Award

    About bioinformatics
    Bioinformatics jobs

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

    All software groups
    FTP repository
    SVN & CVS repositories [?]
    Mailing lists

    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



    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.


    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

    Start a new thread:
    You have to be logged in to post a reply.


    Copyright © 2022 Scilico, LLC · Privacy Policy