Abstract
This paper studies how to perform efficient subphylogeny pattern matching query on a phylogeny. By exploiting the fact that the close species in the phylogeny share many similarities in their DNA sequences, so that we can reduce the space to store these sequences, and applying existing data structures like suffix array, wavelet tree, and heavy path decomposition, we design an indexing structure that takes asymptotically minimal space, while supporting the subphylogeny pattern matching query, efficiently, as desired.