Efficient and Accurate Construction of Genetic Linkage Maps from the Minimum Spanning Tree of a Graph

By Yonghui Wu, Prasanna Bhat, Timothy J. Close, Stefano Lonardi. PLoS Genetics, 2008

541 citations recorded by the source corpus.

Genetic linkage maps are cornerstones of a wide spectrum of biotechnology applications, including map-assisted breeding, association genetics, and map-assisted gene cloning. During the past several years, the adoption of high-throughput genotyping technologies has been paralleled by a substantial increase in the density and diversity of genetic markers. New genetic mapping algorithms are needed in order to efficiently process these large datasets and accurately construct high-density genetic maps. In this paper, we introduce a novel algorithm to order markers on a genetic linkage map. Our method is based on a simple yet fundamental mathematical property that we prove under rather general assumptions. The validity of this property allows one to determine efficiently the correct order of markers by computing the minimum spanning tree of an associated graph. Our empirical studies obtained on genotyping data for three mapping populations of barley (Hordeum vulgare), as well as extensive simulations on synthetic data, show that our algorithm consistently outperforms the best available methods in the literature, particularly when the input data are noisy or incomplete. The software implementing our algorithm is available in the public domain as a web tool under the name MSTmap.

Subfields: Genetics, Plant Science

View Paper: https://www.semanticscholar.org/paper/62bab4fecabfe7b3c74aa9483a1468930c2f8981

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Genetics

1. J. Dubcovsky
2. Kevin P. Smith
3. J. Doležel
4. J. Massman
5. M. Sorrells
6. S. Chao
7. G. Bai
8. G. Brown-Guedira

In Plant Science

1. M. Sorrells
2. S. Chao
3. J. Dubcovsky
4. G. Bai
5. Kevin P. Smith
6. J. Doležel
7. J. Massman
8. Michael O. Pumphrey

Citations in the corpus

• High-throughput linkage mapping of Australian white cypress pine (Callitris glaucophylla) and map transferability to related species (2015, methodology): “…was performed by the MSTmap program, which can attain high accuracy of ordering (Kendall's τ>0.989) in simulated genotype data, when mapping populations whose size (n=100), missing rate (γ=0.10), and error rate (η=0.10) (Wu et al. 2008) are comparable to our raw genotype data (n =74, γ = 0.10).”
• ALLMAPS: robust scaffold ordering based on multiple maps (2015, methodology): “Maps constructed using different software, such as R/QTL [17], MSTMAP [18], and JOINMAP [19], often differ in their final ordering of genetic markers.”
• The minimum spanning tree: An unbiased method for brain network analysis (2015, unknown): “…as dimension reduction method in genetic linkage maps, as a method to partition highways and roads in transport networks, or as way to find the state with the lowest energy or disorder in physical systems (Dussert et al., 1986; Jackson and Read, 2010; King and Tidor, 2009; Wu et al., 2006, 2008).”
• MapDisto: fast and efficient computation of genetic linkage maps (2012, unknown): “2005), CarthaGene (Schiex and Gaspin 1997) and MSTmap (Wu et al. 2008).”
• JCVI: A versatile toolkit for comparative genomics analysis (2024, methodology): “The quality of genome assemblies can be improved by integrating our prior developments from ALLHIC [42], ALLMAPS [24], linkage mapping tools [39], and MCscan outputs and bringing these evidence all under the same framework, as shown in Case III.”
• Genome-wide comparative diversity uncovers multiple targets of selection for improvement in hexaploid wheat landraces and cultivars (2013, methodology): “The linkage maps for the six biparental populations (Dataset S3) were created using the program MSTmap (50).”
• Genome-wide association mapping of Fusarium head blight resistance in contemporary barley breeding germplasm (2011, background): “SNP marker positions were identified on a consensus map by Wu et al. (2008).”
• An Improved Consensus Linkage Map of Barley Based on Flow‐Sorted Chromosomes and Single Nucleotide Polymorphism Markers (2011, methodology): “Since not all the individual maps had the same SNP coverage, we preferred not to force the number of LGs to match the number of chromosomes and to use a set of stringent parameters with MSTMAP, taking advantage of the wealth of genetic map information to link the disjointed LGs. Specifi cally, we us”