Source:http://linkedlifedata.com/resource/pubmed/id/18451426
Switch to
| Predicate | Object |
|---|---|
| rdf:type | |
| lifeskim:mentions | |
| pubmed:issue |
2
|
| pubmed:dateCreated |
2008-5-2
|
| pubmed:abstractText |
A genetic map is an ordering of genetic markers calculated from a population of known lineage. While 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 using the weighted symmetric difference distance, 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 using seven populations of the crop plant Zea mays.
|
| pubmed:language |
eng
|
| pubmed:journal | |
| pubmed:citationSubset |
IM
|
| pubmed:status |
MEDLINE
|
| pubmed:issn |
1545-5963
|
| pubmed:author | |
| pubmed:issnType |
Print
|
| pubmed:volume |
5
|
| pubmed:owner |
NLM
|
| pubmed:authorsComplete |
Y
|
| pubmed:pagination |
161-71
|
| pubmed:dateRevised |
2009-11-3
|
| pubmed:meshHeading | |
| pubmed:articleTitle |
Consensus genetic maps as median orders from inconsistent sources.
|
| pubmed:affiliation |
Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50014, USA. zbbrox@iastate.edu
|
| pubmed:publicationType |
Journal Article,
Research Support, U.S. Gov't, Non-P.H.S.,
Research Support, Non-U.S. Gov't
|