My suspicion is that most queries biologists would make concerning trees are fundamentally LCA queries (as opposed to pattern matching, for example). For instance, "find me trees where group x is monophyletic" is a LCA query. Hence, LCA algorithms of of special interest (especially if they can be incorporated in a database). One recent LCA algorithm due to Bender and Farach-Colton (PDF here) has an implementation available in SourceForge, courtesy of Muhammad Ahsan Yusuf and Zack Ramjan.
There is a recent paper on this work (and the problem of LCA's in directed acyclic graphs) by Bender et al. in Journal of Algorithms(doi:10.1016/j.jalgor.2005.08.001).