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.
authors.affiliation: Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA. gsgk@cs.utexas.edu
authors.forename: Ganeshkumar
authors.initials: G
authors.lastname: Ganapathy
authors.forename: Barbara
authors.initials: B
authors.lastname: Goodson
authors.forename: Robert
authors.initials: R
authors.lastname: Jansen
authors.forename: Hai-Son
authors.initials: HS
authors.lastname: Le
authors.forename: Vijaya
authors.initials: V
authors.lastname: Ramachandran
authors.forename: Tandy
authors.initials: T
authors.lastname: Warnow
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D003710:Demography; D008957:Models, Genetic; D010363:Pattern Recognition, Automated / Q000379:methods*; D010802:Phylogeny; D011157:Population Dynamics