Analysis of Biological and Archeological Data



next up previous
Next: Solution Approaches Up: Sample Applications Previous: Pattern Matching

Analysis of Biological and Archeological Data

In biology and archeology, a standard model for relating objects is that of a tree. Trees can represent the division of a species into two separate species or the division of features of some artifact (like pottery or pins). Species do not come with histories, however, nor are artifacts completely dated. Therefore, it is necessary to deduce the tree structure from the features of the items.

One approach to this is to create a distance measure between the items. If the distance measure represents distances along a tree, then that tree is a good estimate for the underlying, ``real'' tree. Normally, the distances do not represent a tree, so it is necessary to find a tree that accurately estimates the true distances. One approach to this, suggested by Barthélemy and Guénoche [11], creates a graph as follows: the nodes of the graph represent partitions of the items. These partitions are chosen because items within a partition are closer to each other than to those in the other side of the partition. Two nodes are adjacent if the partitions are consistent with coming from the same tree (which reduces to an inclusion condition). A clique in this graph represents a set of partitions that can be formed into a tree. Maximum cliques attempt to encapsulate as much of the partition data as possible. For more information, see Chapter 5 of [11].



Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994