Consensus Genetic Maps as Median Orders from Inconsistent Sources
Authors:
- Benjamin N. JacksonBJBenjamin N. Jackson
- Patrick S. SchnablePSPatrick S. Schnable
- Srinivas AluruSASrinivas Aluru
- 7 May 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 5 (2) , 161-171
Abstract
A genetic map is an ordering of genetic markers calculated from a population of known lineage. Although, traditionally, a map has been generated from a single population for each species, recently, researchers have created maps from multiple populations. In the face of these new data, we address the need to find a consensus map - a map that combines the information from multiple partial and possibly inconsistent input maps. We model each input map as a partial order and formulate the consensus problem as finding a median partial order. Finding the median of multiple total orders (preferences or rankings) is a well-studied problem in social choice. We choose to find the median by using the weighted symmetric difference distance, which is a more general version of both the symmetric difference distance and the Kemeny distance. Finding a median order using this distance is NP-hard. We show that, for our chosen weight assignment, a median order satisfies the positive responsiveness, extended Condorcet, and unanimity criteria. Our solution involves finding the maximum acyclic subgraph of a weighted directed graph. We present a method that dynamically switches between an exact branch and bound algorithm and a heuristic algorithm and show that, for real data from closely related organisms, an exact median can often be found. We present experimental results by using seven populations of the crop plant Zea mays.Keywords
This publication has 25 references indexed in Scilit:
- Genetic Dissection of Intermated Recombinant Inbred Lines Using a New Genetic Map of MaizeGenetics, 2006
- Cis-effects on Meiotic Recombination Across Distinct a1-sh2 Intervals in a Common Zea Genetic BackgroundSequence data from this article have been deposited with the EMBL/GenBank Data Libraries under accession nos. AY656756, AY656757, AY656758 and AY662984, AY662985, AY662986, AY662987.Genetics, 2005
- Efficient sorting of genomic permutations by translocation, inversion and block interchangeBioinformatics, 2005
- Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrierJournal of the ACM, 2005
- Fast and high precision algorithms for optimization in large-scale genomic problemsComputational Biology and Chemistry, 2004
- Transforming cabbage into turnipJournal of the ACM, 1999
- A fast and effective heuristic for the feedback arc set problemInformation Processing Letters, 1993
- MAPMAKER: An interactive computer package for constructing primary genetic linkage maps of experimental and natural populationsGenomics, 1987
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975
- Fair and reasonable election systemsSystems Research and Behavioral Science, 1975