DIMACS Tutorial on Bioconsensus II

October 2, 2001
DIMACS Center, CoRE Building, Rutgers University, Piscataway, NJ

Tutorial Organizers:
Fred McMorris, Illinois Institute of Technology, mcmorris@iit.edu
William H.E. Day, whday@istar.ca
Presented under the auspices of the Special Year on Computational Molecular Biology.

Tutorial Program

Tuesday October 2, 2001


8:15-8:50     Breakfast and Registration

8:50-9:00     Welcome and Greeting: 
              Mel Janowitz, DIMACS Associate Director

9:00-10:30    Tutorial: William H.E. Day

10:30-11:00   Break

11:00-12:30   Tutorial: William H.E. Day

12:30-1:30    Lunch

1:30-3:00     Tutorial: Fred McMorris, Illinois Institute of Technology

3:00-3:30     Break

3:30-4:00     Tutorial: Fred McMorris, Illinois Institute of Technology

4:00-4:45     Questions and Discussion - Day and McMorris

5:00-         Van Returns to Holiday Inn


ABSTRACT:

Axiomatics in Bioconsensus, Classification and Group Choice

William H. E. Day
P.O. Box 17, Port Maitland, NS B0W 2V0, Canada
E-mail: whday@istar.ca

F. R. McMorris
Department of Applied Mathematics
Illinois Institute of Technology, Chicago, IL 60616--3793
E-mail: mcmorris@iit.edu


Axiomatic analyses of problems establish a precise qualitative framework of reasoning, and they may reveal how valuable (sometimes unexpected) conclusions follow from given initial assumptions. In this tutorial we will explore how axiomatizations may be used to investigate consensus problems in group choice, classification, clustering, and the alignment of sequences. The topics will include how axiomatizations can establish the nonexistence of suitable consensus rules, or the existence of unique rules or families of rules. The consensus rules discussed will include the majority and plurality rules, median procedures, and rules based on concepts of center and mean. The objects on which these consensus rules act will include weak orderings of preferences, partitions of a set, hierarchies (rooted trees with labeled leaves), undirected phylogenetic trees, and molecular sequences.

The tutorial will include a three-hour presentation by Day, a two-hour presentation by McMorris, and one hour of spontaneous general discussions.

Day will introduce basic concepts and paradigms for investigating consensus problems in the biological sciences. A useful approach is to formulate a set of axioms, or properties, that reasonable researchers would accept as desirable, then to determine the set of consensus rules satisfying these axioms. Using stronger (but compelling) axioms based on concepts of independence or unanimity may yield a restricted class of consensus rules having undemocratic (undesirable?) properties based on dictatorships or oligarchies. Using weaker axioms based on concepts of neutrality or monotonicity may yield characterizations of unique consensus rules or families of rules. Many relevant examples will be given. Day's presentation will conclude with a brief discussion of order-theoretic frameworks for axiomatic characterizations.

McMorris will pick up where Day's presentation ends. He will first discuss consensus functions on graphs by focusing on the center, median and mean functions. Characterizations (when known) and open problems will be given. McMorris will then discuss consensus methods for molecular sequences based on plurality, mean and median functions. McMorris's presentation will conclude by tying this in to an iterative approach to multiple sequence alignment using consensus.

Attendees should have a reasonable mathematical maturity, a tolerance for mathematical abstraction, and an interest in how mathematics can be used to model aspects of biological problems. Each attendee will receive a copy of the lecture notes and a bibliography of relevant literature.


Other Workshops
DIMACS Homepage
Contacting the Center
Document last modified on October 2, 2001.