DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Thirty Seven
TITLE: "Mathematical Hierarchies and Biology"
EDITORS: Boris Mirkin, F. R. McMorris, Fred S. Roberts and Andrey Rzhetsky.

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


The mathematical approach to the study of hierarchies presents the theoretical basis for many important areas of current scientific investigation. Biology has benefited from this research and has also stimulated the mathematical study of hierarchies.

This collection presents papers devoted to theoretical, algorithmical, and application issues related to (1) reconstructing hierarchies (trees or ranking) from (dis)similarity or entity-to-character data, (2) using hierarchies for modeling evolution and other processes, and (3) combining (gene) trees.

The papers in this volume provide a contemporary sample of many new results in hierarchy theory with applications in biology, psychology, data analysis, and systems engineering.



Foreword							 ix

Preface								 xi

Ancestor-descendant relations and incompatible data: 
  Motivation for research in discrete mathematics
    G. F. Estabrook						  1

Krohn-Rhodes theory, hierarchies & evolution
    C. L. Nehaniv and J. Rhodes					 29

Inferring evolutionary trees from polymorphic characters, 
  and an analysis of the Indo-European family of languages
    M. L. Bonet, C. A. Phillips, T. J. Warnow, and S. Yooseph 	 43

Reconciled trees and incongruent gene and species trees
    R. D. Page and M. Charleston				 57

Comparison of annotating duplication, tree mapping, and 
  copying as methods to compare gene trees with species trees
    O. Eulenstein, B. G. Mirkin, and M. Vingron			 71

Fitting models of intron evolution to aldehyde dehydrogenase 
    A. Rzhetsky, F. J. Ayala, L. C. Hsu, C. Chang, and 
    A. Yoshida							 95

Dissimilarity maps and substitution models: Some new results
    V. L. Moulton, M. A. Steel, and C. Tuffley			111

The performance of the neighbor-joining method of phylogeny 
    K. Atteson							133

Concerning the NJ algorithm and its unweighted version, UNJ
    O. Gascuel							149

Order distances in tree reconstruction
    A. Guenoche							171

Circular orders of tree metrics, and their uses for the 
  reconstruction and fitting of phylogenetic trees
    V. Makarenkov and B. Leclerc				183

Estimation of missing distances in path-length matrices: 
  Problems and solutions
    P.-A. Landry and F.-J. Lapointe 				209

Complexity issues in hierarchical optimization
    P. M. Pardalos and X. Deng					219

  P. Hansen and D. de Werra					225

Phylogeny graphs of arbitrary digraphs
    F. S. Roberts and L. Sheng 					233

Agreement metrics for trees revisited
    E. M. Kubicka, G. Kubicki, and F. R. McMorris 		239

Sparse dynamic programming for maximum agreement subtree 
    T. M. Przytycka						249

The median function on weak hierarchies
    F. R. McMorris and R. C. Powers				265

Towards a theory of holistic clustering
    A. W. Dress							271

On hierarchies and hierarchical classes models
    I. Van Mechelen, S. Rosenberg, and P. De Boeck		291

The construction of globally optimal ordered partitions
    L. Hubert, P. Arabie, and J. Meulman			299

Multiple trees: Fitting two or more tree structures to 
  proximity data
    D. Carroll and G. De Soete					313

Linear embedding of binary hierarchies and its applications
    B. G. Mirkin						331

Learning algorithms generating multigranular hierarchies
    A. Meystel							357

Index								385

Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.