TSPmap

TSPmap constructs genetic linkage maps by leveraging approximate and exact solutions to the Traveling Salesperson Problem (TSP) to optimize marker order for genome assembly refinement and trait mapping.

Key Features:

• Integration of TSP solvers: Implements both approximate and exact algorithms for the Traveling Salesperson Problem (TSP) to determine marker order for linkage map construction.
• Handling large marker datasets: Designed to process extensive marker datasets, explicitly applied to datasets of upwards of 10,000 genomic markers.
• Robustness to genotyping errors: Demonstrates resilience to missing and erroneous genotyping data when generating linkage maps.
• Versatility across population types: Applicable to various population types derived from inbred parents.
• Comparison to traditional methods: Reported to maintain robustness relative to traditional linkage-mapping methods such as JoinMap and MSTmap.

Scientific Applications:

• Genome assembly refinement: Produces ordered linkage maps used to improve and validate genome assemblies.
• Trait-mapping and genetic analysis: Facilitates mapping of trait variation in ecologically and agriculturally significant species.
• High-resolution genetic mapping: Enables construction of dense linkage maps from large-scale marker datasets for downstream genetic and breeding studies.

Methodology:

Leverages both approximate and exact TSP solvers to optimize marker order and generate genetic linkage maps, applied to large marker datasets and tolerant of missing or erroneous genotype data.