tspOrder: Order markers within linkage groups

In mckaylab/TSPmap: A tool making use of traveling salesperson problem solvers in the efficient and accurate construction of high-density genetic linkage maps

Description

tspOrder Apply a traveling salesperson problem solver to find the shortest path through the recombination fraction matrix. Requires that the TSP package is installed. Optimal performance is provided by the "Concorde" method; however, this requires independent installation of the Concorde program. See details.

Usage

tspOrder(cross, method = "concorde", hamiltonian = TRUE,
  concorde_path = NULL, return = "cross")

Arguments

cross	The QTL cross object.
method	The solve_TSP method to employ. We highly encourage using method = "condcorde". Simulations show that this method outperforms all others significantly. See details.
hamiltonian	Logical, should a hamiltonian circuit be enforced?
concorde_path	Required if method = "concorde". The directory containing concorde executables.
return	If "cross" is specified, pass the marker order through newLG, which quickly reorders the markers of the original cross to follow the TSP order. Otherwise, return a named list of markers in order for each chromosome.
...	Additional arguments passed on to solve_TSP that are then paseed to TSP::contol.

Details

This function relies on the TSP R packages to perform the TSP solvers. See documentation therein, esspecially the function TSP::solve_TSP. We permit inference of marker order within a Hamiltonian circuit by adding a dummy node that has 0 distance to all other nodes. This allows for discrete start and end points and is more appropriate for genetic map construction than forcing a complete route through all markers.

The best performance seems to result from using hamiltonian = T and method = "concorde".

We recommend using the concorde algorithm. To do this, install the concorde program: http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/src/co031219.tgz. If on a mac, this is not super easy. See https://qmha.wordpress.com/2015/08/20/installing-concorde-on-mac-os-x/ for details on the best way to do this.

Value

Either a cross object with reordered markers, or a named list of markers in a new order.

Examples

library(qtlTools)
data(fake.f2)
cross<-fake.f2
## Not run: 
fake.f2<-est.rf(fake.f2)
cross<-fake.f2
#Perturb the marker order and chromosome names
markerlist<-lapply(chrnames(cross), function(x) sample(markernames(cross, chr =x)))
names(markerlist)<-as.character(chrnames(cross))
cross2<-newLG(cross, markerList = markerlist)
library(TSP)
plot.rf(cross2)
cross3<-cross3<-tspOrder(cross = cross2,
  hamiltonian = T,
  method="nn") # change to your path
cross3<-cross3<-tspOrder(cross = cross2,
  hamiltonian = T,
  method="concorde",
  concorde_path = "/Users/John/Documents/concorde/TSP") # change to your path
plot.rf(cross3)

## End(Not run)

mckaylab/TSPmap documentation built on Aug. 19, 2021, 8:38 p.m.