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
Fred R. McMorris
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 power 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 phylogenetics 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 studies F.-J. Lapointe and G. Cucumel 205 Increasing phylogenetic accuracy with global congruence C. Levasseur and F.-J. Lapointe 221 MRP supertree construction in the consensus setting O. R. P. Bininda-Emonds 231