Keywords

phylogenetic analysis, NP-Hard problem, trees

Abstract

Phylogenetic analysis is becoming an increasingly important tool for biological research. Applications include epidemiological studies, drug development, and evolutionary analysis. Phylogenetic search is a known NP-Hard problem. The size of the data sets which can be analyzed is limited by the exponential growth in the number of trees that must be considered as the problem size increases. A better understanding of the problem space could lead to better methods, which in turn could lead to the feasible analysis of more data sets. We present a definition of phylogenetic tree space and a visualization of this space that shows significant exploitable structure. This structure can be used to develop search methods capable of handling much larger datasets.

Original Publication Citation

On the Use of Cartographic Projections in Visualizing Phylogenetic Tree Space, Kenneth Sundberg, Mark Clement and Quinn Snell, Algorithms for Molecular Biology 21, 5:26 (8 June 21).