IDEAS home Printed from https://ideas.repec.org/a/plo/pgen00/1000212.html
   My bibliography  Save this article

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

Author

Listed:
  • Yonghui Wu
  • Prasanna R Bhat
  • Timothy J Close
  • Stefano Lonardi

Abstract

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

Suggested Citation

  • Yonghui Wu & Prasanna R Bhat & Timothy J Close & Stefano Lonardi, 2008. "Efficient and Accurate Construction of Genetic Linkage Maps from the Minimum Spanning Tree of a Graph," PLOS Genetics, Public Library of Science, vol. 4(10), pages 1-11, October.
  • Handle: RePEc:plo:pgen00:1000212
    DOI: 10.1371/journal.pgen.1000212
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosgenetics/article?id=10.1371/journal.pgen.1000212
    Download Restriction: no

    File URL: https://journals.plos.org/plosgenetics/article/file?id=10.1371/journal.pgen.1000212&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pgen.1000212?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Cunmin Qu & Meichen Zhu & Ran Hu & Yongchao Niu & Si Chen & Huiyan Zhao & Chengxiang Li & Zhen Wang & Nengwen Yin & Fujun Sun & Zhiyou Chen & Shulin Shen & Guoxia Shang & Yan Zhou & Xingying Yan & Lij, 2023. "Comparative genomic analyses reveal the genetic basis of the yellow-seed trait in Brassica napus," Nature Communications, Nature, vol. 14(1), pages 1-16, December.
    2. Taylor, Julian & Butler, David, 2017. "R Package ASMap: Efficient Genetic Linkage Map Construction and Diagnosis," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 79(i06).
    3. Alexander Coulton & Alexandra M Przewieslik-Allen & Amanda J Burridge & Daniel S Shaw & Keith J Edwards & Gary L A Barker, 2020. "Segregation distortion: Utilizing simulated genotyping data to evaluate statistical methods," PLOS ONE, Public Library of Science, vol. 15(2), pages 1-19, February.
    4. Bastian Schiffthaler & Carolina Bernhardsson & Pär K Ingvarsson & Nathaniel R Street, 2017. "BatchMap: A parallel implementation of the OneMap R package for fast computation of F1 linkage maps in outcrossing species," PLOS ONE, Public Library of Science, vol. 12(12), pages 1-12, December.
    5. Qingsong Zhao & Jun Qin & Xinxin Li & Bingqiang Liu & Yang Liu & Qing Yang & Song Liu & Xin Zhao & Niannian Ma & Long Yan & Mengchen Zhang & Chunyan Yang & Hong Liao, 2022. "Coordinate Inheritance of Seed Isoflavone and Protein in Soybean," Agriculture, MDPI, vol. 12(8), pages 1-24, August.
    6. Yong Zhou & Zhichao Yu & Dmytro Chebotarov & Kapeel Chougule & Zhenyuan Lu & Luis F. Rivera & Nagarajan Kathiresan & Noor Al-Bader & Nahed Mohammed & Aseel Alsantely & Saule Mussurova & João Santos & , 2023. "Pan-genome inversion index reveals evolutionary insights into the subpopulation structure of Asian rice," Nature Communications, Nature, vol. 14(1), pages 1-14, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pgen00:1000212. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosgenetics (email available below). General contact details of provider: https://journals.plos.org/plosgenetics/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.