Fast Structural Search in Phylogenetic Databases

Abstract: As the size of phylogenetic databases grows, the need for effi ciently searching these databases arises. Thanks to previous and ongoing research, searching by attribute value and by text has become commonplace in these databases. However, searching by topological or physical structure, especially for large databases and especially for approximate matches, is still an art. We propose structural search techniques that, given a query or pattern tree P and a database of phy-logenies D, fi nd trees in D that are suffi ciently close to P. The “closeness ” is a measure of the topological relationships in P that are found to be the same or similar in a tree D in D. We develop a fi ltering technique that accelerates searches and present algorithms for rooted and unrooted trees where the trees can be weighted or unweighted. Experimental results on comparing the similarity measure with existing tree metrics and on evaluating the effi ciency of the search techniques dem-onstrate that the proposed approach is promising