DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Sixty One
TITLE: "Bioconsensus"
EDITORS: M. F. Janowitz, F.-J. Lapointe, F. R. McMorris, B. Mirkin and F.S. Roberts

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.


Consensus methods developed in the context of voting, decision making, and other areas of the social and behavioral sciences have begun to have a variety of applications in the biological sciences, originally in taxonomy and evolutionary biology, and more recently in molecular biology. Typically, several alternatives (such as alternative phylogenetic trees, molecular sequences, or alignments) are produced using different methods or under different models, and then one needs to find a consensus solution. There are, already, several hundred papers in this developing field of "Bioconsensus." We hope that this volume will provide a valuable introduction and reference to various aspects of the subject

This volume is based on two DIMACS working group meetings on Bioconsensus that were held at DIMACS on October 25-26, 2000 and October 2-5, 2001. The goals of the meetings were to gather together a diverse group of researchers from Mathematics, Statists, Biology and Computer Science with the idea of exploring which biological concepts could benefit from concepts and methods of consensus theory,as well as the extent to which consensus methods from social choice theory might apply to problems in evolutionary biology and other areas of the biological sciences. The formal sessions were kept to a minimum so as to allow ample time for discussions and actual research. We should mention, however, that this volume is more than just a Proceedingd of two workshops. It includes invited papers that were not part of the working group meetings, as well as expansions of talks that were presented at the two meetings. It is anticipated that the two survey papers will provide a valuable guide to the aready vast literature in this area.

Issues such as the following were typical of those that were discussed: computational complexity of various consensus algorithms, the role of supertrees in evolutionary biology, the extent to which techniques from social choice theory can be modified to be useful in molecular biology,s tudy of aciomatic properties of consensus methods, the importance of choosing consensus methods based on biological rather than mathematical properties, the extent to which consensus methods even make sense in connection with the reconstruction of evolutionary biology

There are a total of 16 papers in the volume. They are difficult to classify by area of author expertise because many of them are joint papers written by authors from different fields. We chose instead to divide them into three general areas. The section on axiomatic considerations is more theoretical than the rest of the volume, and contains five papers. The papers leaning toward computer science approaches can be found in the next section on data analysis, and consists of another five papers. The final part deals more with phylogenetic techniques and has in it the remaining six papers.

The working group meetings that formed the basis for this volume were part of the DIMACS 2000-2003 Special Focus on Computational Molecular Biology. Funding was provided by the Alfred P. Sloan Foundation, Celera Genomics, the National Science Foundation, the New Jersey Commission on Science and Technology, IBM, and SmithKline Beecham. The editos wish to express their thanks for this support.

Melvin F. Janowitz
Francois-Joseph Lapointe
Fred R. McMorris
Boris Mirkin
F.S. Roberts


Forward                                                vii

Preface                                                 ix

          Part I. Axiomatic considerations 

Axiomatics in group choice and bioconsensus
     W. H. E. Day and F. R. McMorris                     3

The Arrovian program from weak orders to hierarchical
   and tree-like relations
     F. R. McMorris and R. C. Powers                    37

Consensus $n$-trees, weak independence, and veto
     R. C. Powers                                       47

The size of a maximum agreement subtree for random
   binary trees
     D. Bryant, A. McKenzie, and M. Steel               55

An injective set representation of closed systems
   of sets
     G. D. Crown and M. F. Janowitz                     67

       Part II. Data analysis considerations 

Consensus list colorings of graphs and physical
   mapping of DNA 
     N. V. R. Mahadev and F. S. Roberts                 83

A top-down method for building genome classification
   trees with linear binary hierarchies
     B. Mirkin and E. Koonin                            97

An application of seriation to agent development
   consensus: A genetic algorithm approach
     M. L. Gargano, W. Edelson, and J. DeCicco         113

Achieving consensus of long genomic sequences with
   the W-curve
     D. J. Cork                                        123

Flipping: A supertree construction method
     D. Chen, L. Diao, O. Eulenstein, D. Fernandez-
     Baca, and M. Sanderson                            135

         Practical considerations 

A classification of consensus methods for
     D. Bryant                                         163

A view of supertree methods
     J. L. Thorley and M. Wilkinson                    185

Reduced consensus
     M. Wilkinson and J. L. Thorley                    195

How good can a consensus get? Assessing the
   reliability of consensus trees in phylogenetic
     F.-J. Lapointe and G. Cucumel                     205

Increasing phylogenetic accuracy with global
     C. Levasseur and F.-J. Lapointe                   221

MRP supertree construction in the consensus setting
     O. R. P. Bininda-Emonds                           231

Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on April 15, 2003.