@inproceedings{943386b36cb64e3a9813f33a221dc7eb,
title = "TreeRank: A similarity measure for nearest neighbor searching in phylogenetic databases",
abstract = "Phylogenetic trees are unordered labeled trees in which each leaf node has a label and the order among siblings is unimportant. In this paper we propose a new similarity measure, called TreeRank, for phylogenetic trees and present an algorithm for computing TreeRank scores. Given a query or pattern tree P and a data tree D, the TreeRank score from P to D is a measure of the topological relationships in P that are found to be the same or similar in D. The proposed algorithm calculates the TreeRank score in O(M2 + N) time where M is the number of nodes appearing in both P and D, and N is the number of nodes in D. We then develop a search engine that, given a query or pattern tree P and a database of trees D, finds and ranks the nearest neighbors of P in D where the {"}nearness{"} is measured by the proposed similarity function. This structure-based search engine is fully operational and is available on the World Wide Web.",
keywords = "Biology, Computer science, Data analysis, Databases, Educational institutions, Information retrieval, Nearest neighbor searches, Phylogeny, Search engines, Web sites",
author = "Wang, {J. T.L.} and Huiyuan Shan and D. Shasha and Piel, {W. H.}",
note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 15th International Conference on Scientific and Statistical Database Management, SSDBM 2003 ; Conference date: 09-07-2003 Through 11-07-2003",
year = "2003",
doi = "10.1109/SSDM.2003.1214978",
language = "English (US)",
series = "Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM",
publisher = "IEEE Computer Society",
pages = "171--180",
editor = "Silvia Nittel and Dimitrios Gunopulos",
booktitle = "15th International Conference on Scientific and Statistical Database Management, SSDBM 2003",
}