Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Encodings of cladograms and labeled trees. | Encodings of cladograms and labeled trees Daniel J. Ford Google Inc. 1600 Amphitheatre Pkwy Mountain View CA USA 94043 ford@ Submitted May 17 2008 Accepted Mar 22 2010 Published Mar 29 2010 Mathematics Subject Classification 05C05 05C85 Abstract This paper deals with several bijections between cladograms and perfect matchings. The first of these is due to Diaconis and Holmes. The second is a modification of the Diaconis-Holmes matching which makes deletion of the largest labeled leaf correspond to gluing together the last two points in the perfect matching. The third is an entirely new encoding of cladograms first as a bijection with a certain set of strings and then via this to perfect matchings. In this pair of bijections deletion of the largest labeled leaf corresponds to deletion of the corresponding symbols from the string or deletion of the corresponding pair from the matching. These two new bijections are related through a common max-min labeling of internal vertices with two different choices for the label of the root node. All these encodings are extended to cladograms with edge lengths and left-right ordered children. Moving a single symbol in this last encoding corresponds to a subtree prune and regraft operation on the cladogram making it well suited for use in phylogentics software. Finally a perfect Gray code for cladograms is derived from the bar encoding along with a total ordering on all cladograms Algorithms are also provided for finding the next and previous cladogram the cladogram at any position and the position of any cladogram in the sequence. A cladogram with n leaves is a rooted binary leaf labeled tree with leaves distinctly labeled 1 . n. It has long been known that the number of such trees with exactly n leaves is 2n 3 . This is also the number of perfect matchings on 2 n 1 points. Diaconis and Holmes give a bijection in 7 between the set of cladograms and perfect matchings. Research supported by Stanford Mathematics Department
