Plant & Animal Genomes XIII Conference

January 15-19, 2005
Town & Country Convention Center
San Diego, CA

Multilocus Consensus Genetic Maps: Formulation, Algorithms, And Results

David Mester , Yefim Ronin , Dina Minkov , Michael Korostishevsky , Abraham Korol

  Institute of Evolution, University of Haifa, Mount Carmel, Haifa, 31905, Israel

Problem formulation: (a) Multilocus genetic maps with "dominance"complication. The problem is
connected with building of genetic maps using F2 data with dominant markers in repulsion phase.
In such situations we split the marker set into two groups, each containing dominant markers in
coupling phase and shared codominant markers. Multlocus maps are then ordered for the two sets
with a constraint that shared markers should have equal order in the two maps. The last step is
merging two maps into a resulting one. (b) Multilocus genetic maps with sexual differences in
recombination. These maps are built using male and female recombination rates represented as
sex-specific matrices. Sex-dependence of "distance" matrix may force optimization algorithm to
produce different marker orders (maps); thus, our goal is to find the optimal solution under
the restriction of same order in two maps. (c) Building consensual multilocus maps. Most of the
current attempts to build consensus maps are based on search of common (shared) orders in the
previously (independently) constructed maps. Instead, we propose to build consensus maps by
RE-ANALYSIS of initial data with testing the reliability of the maps using computing-intensive
resembling procedures (jackknife/bootstrap). Arbitrary patterns of shared subsets of markers
may be characteristic of the data.
Algorithms: We have demonstrated the usefulness of considering multilocus ordering in terms of
the mathematical formulation known as Traveling Salesperson Problem (TSP). Our powerful Guided
Evolutionary Strategy (GES) heuristics proved very efficient for multlocus ordering. In contrast
to this standard genetic marker ordering for one data set, multilocus ordering of multiple sets
with the requirement of shared ordering for shared markers should be considered as a special
and difficult for treatment TSP-like formulation (that can be referred to as "synchronized-TSP").
We developed new GES algorithms for discrete optimization, and adapted these to synchronized-TSP
for constructing consensus maps. The algorithms were checked on simulated data and real data on
cereals. The proposed methodology will be illustrated using our new MultiPoint software package.