@article{48258dff04dd441bb81931e230efd222,
title = "Pattern identification in biogeography",
abstract = "Identifying common patterns among area cladograms that arise in historical biogeography is an important tool for biogeographical inference. We develop the first rigorous formalization of these pattern-identification problems. We develop metrics to compare area cladograms. We define the maximum agreement area cladogram (MAAC) and we develop efficient algorithms for finding the MAAC of two area cladograms, while showing that it is NP-hard to find the MAAC of several binary area cladograms. We also describe a linear-time algorithm to identify if two area cladograms are identical.",
keywords = "Area cladograms, Biogeography, Distance metrics, Maximum agreement area cladogram, Maximum agreement subset",
author = "Ganeshkumar Ganapathy and Barbara Goodson and Robert Jansen and Le, {Hai Son} and Vijaya Ramachandran and Tandy Warnow",
note = "Funding Information: The research of Geneshkumar Ganapathy was supported by US National Science Foundation (NSF) grants 0331453 and 0121680, Hai-son Le by an Undergraduate Research Opportunity Program (UROP) grant from the Computer Sciences Department at the University of Texas at Austin, Vijaya Ramachandran by NSF grant CCF-0514876, Tandy Warnow by NSF grants 0331453, 0312830, and 0121680, Barbara Goodson by NSF IGERT training grant 0114387, and Robert Jansen by NSF grant DEB 0120709. Funding Information: Tandy Warnow received the PhD degree in mathematics from the University of California at Berkeley under the direction of Gene Lawler and did postdoctoral training with Simon Tavare and Michael Waterman at the University of Southern California. She is a professor of computer sciences at the University of Texas at Austin. Her research combines mathematics, computer science, and statistics to develop improved models and algorithms for reconstructing complex and large-scale evolutionary histories in both biology and historical linguistics. She received the US National Science Foundation (NSF) Young Investigator Award in 1994 and the David and Lucile Packard Foundation Award in Science and Engineering in 1996. She is a member of five graduate programs at the University of Texas, including computer science; ecology, evolution, and behavior; molecular and cellular biology; mathematics; and computational and applied mathematics. She is also one of the co-PI{\textquoteright}s for the multidisciplinary CIPRES (Cyber-Infrastructure for Phylogenetic Research) Project, currently funded by the NSF under their Information Technology Program.",
year = "2006",
month = oct,
doi = "10.1109/TCBB.2006.57",
language = "English (US)",
volume = "3",
pages = "334--346",
journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",
issn = "1545-5963",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",
}