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
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
Index of Volumes
DIMACS Homepage