Send to

Choose Destination
BioData Min. 2017 Dec 19;10:38. doi: 10.1186/s13040-017-0158-0. eCollection 2017.

TSPmap, a tool making use of traveling salesperson problem solvers in the efficient and accurate construction of high-density genetic linkage maps.

Author information

Department of Bioagricultural Sciences & Pest Management, Colorado State University, 1177 Campus Delivery, Fort Collins, CO 80523 USA.
Department of Computer Sciences, Colorado State University, Fort Collins, CO 80523 USA.
Genome Sequencing Center, HudsonAlpha Institute for Biotechnology, Huntsville, AL 35806 USA.
Contributed equally



Recent advances in nucleic acid sequencing technologies have led to a dramatic increase in the number of markers available to generate genetic linkage maps. This increased marker density can be used to improve genome assemblies as well as add much needed resolution for loci controlling variation in ecologically and agriculturally important traits. However, traditional genetic map construction methods from these large marker datasets can be computationally prohibitive and highly error prone.


We present TSPmap, a method which implements both approximate and exact Traveling Salesperson Problem solvers to generate linkage maps. We demonstrate that for datasets with large numbers of genomic markers (e.g. 10,000) and in multiple population types generated from inbred parents, TSPmap can rapidly produce high quality linkage maps with low sensitivity to missing and erroneous genotyping data compared to two other benchmark methods, JoinMap and MSTmap. TSPmap is open source and freely available as an R package.


With the advancement of low cost sequencing technologies, the number of markers used in the generation of genetic maps is expected to continue to rise. TSPmap will be a useful tool to handle such large datasets into the future, quickly producing high quality maps using a large number of genomic markers.


Genetic mapping; Genomic markers; Genotyping by sequencing; Linkage; Next generation sequencing; Travelling salesperson problem

Conflict of interest statement

Not applicableNot applicableThe authors declare that they have no competing interests.Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplemental Content

Full text links

Icon for BioMed Central Icon for PubMed Central
Loading ...
Support Center