Least Common Ancestor (LCA) queries

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).