+1 Recommend
0 collections
      • Record: found
      • Abstract: found
      • Article: not found

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

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          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 MST map.

          Author Summary

          Genetic linkage maps are cornerstones of a wide spectrum of biotechnology applications. In recent years, new high-throughput genotyping technologies have substantially increased the density and diversity of genetic markers, creating new algorithmic challenges for computational biologists. In this paper, we present a novel algorithmic method to construct genetic maps based on a new theoretical insight. Our approach outperforms the best methods available in the scientific literature, particularly when the input data are noisy or incomplete.

          Related collections

          Most cited references 28

          • Record: found
          • Abstract: not found
          • Article: not found

          Genetic Algorithms in Search: Optimization and Machine Learning

            • Record: found
            • Abstract: found
            • Article: not found

            CARHTA GENE: multipopulation integrated genetic and radiation hybrid mapping.

            CAR(H)(T)A GENE: is an integrated genetic and radiation hybrid (RH) mapping tool which can deal with multiple populations, including mixtures of genetic and RH data. CAR(H)(T)A GENE: performs multipoint maximum likelihood estimations with accelerated expectation-maximization algorithms for some pedigrees and has sophisticated algorithms for marker ordering. Dedicated heuristics for framework mapping are also included. CAR(H)(T)A GENE: can be used as a C++ library, through a shell command and a graphical interface. The XML output for companion tools is integrated. The program is available free of charge from www.inra.fr/bia/T/CarthaGene for Linux, Windows and Solaris machines (with Open Source). tschiex@toulouse.inra.fr.
              • Record: found
              • Abstract: found
              • Article: not found

              Construction of multilocus genetic linkage maps in humans.

              Human genetic linkage maps are most accurately constructed by using information from many loci simultaneously. Traditional methods for such multilocus linkage analysis are computationally prohibitive in general, even with supercomputers. The problem has acquired practical importance because of the current international collaboration aimed at constructing a complete human linkage map of DNA markers through the study of three-generation pedigrees. We describe here several alternative algorithms for constructing human linkage maps given a specified gene order. One method allows maximum-likelihood multilocus linkage maps for dozens of DNA markers in such three-generation pedigrees to be constructed in minutes.

                Author and article information

                Role: Editor
                PLoS Genet
                PLoS Genetics
                Public Library of Science (San Francisco, USA )
                October 2008
                October 2008
                10 October 2008
                : 4
                : 10
                [1 ]Department of Computer Science and Engineering, University of California Riverside, Riverside, California, United States of America
                [2 ]Department of Botany and Plant Sciences, University of California Riverside, Riverside, California, United States of America
                Princeton University, United States of America
                Author notes

                Conceived and designed the experiments: YW TJC SL. Performed the experiments: YW PRB. Analyzed the data: YW PRB TJC. Contributed reagents/materials/analysis tools: YW PRB TJC SL. Wrote the paper: YW PRB TJC SL.

                Wu et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
                Page count
                Pages: 11
                Research Article
                Computational Biology/Population Genetics
                Computer Science/Numerical Analysis and Theoretical Computing
                Genetics and Genomics/Bioinformatics
                Genetics and Genomics/Population Genetics



                Comment on this article