Computes the minimal number of inversions required to sort a signed permutation using the Hannenhalli and Pevzner algorithm.
Arguments
- x
Either a GBreaks object or a signed permutation vector. If
xis a GBreaks object, a permutation vector will be extracted usingpermutationVector.
Details
This function uses several helper functions defined in breakpointGraph.R (e.g., extendedPermutation,
breakpoint_graph, hurdles_count, superhurdles_count, and others) to
compute properties of the breakpoint graph and identify cycles, hurdles and superhurdles.
It also depends on permutationVector(), which is defined in permutationVector.R.
This algorithm was designed to work in a single, linear chromosome alignment. Although the function still works if the GBreaks object involves more than one chromosome, the returned value for the minimal number of inversions will imply in non-usual inversions if different chromosomes have orthologous regions.
References
Hannenhalli, Sridhar, and Pavel A. Pevzner. "Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals." Journal of the ACM (JACM) 46.1 (1999): 1-27.
See also
permutationVector for generating the permutation vector.
Other Rearrangement distances:
breakpointGraphProperties(),
inversionEstimate_BD()
Other Similarity indexes:
F81_distance(),
GOC(),
HKY85_distance(),
JC69_distance(),
K80_distance(),
K80_gap_distance(),
P_distance(),
T92_distance(),
TN93_distance(),
breakpointGraphProperties(),
correlation_index(),
inversionEstimate_BD(),
karyotype_index(),
logDet_distance(),
slidingWindow(),
strand_randomisation_index(),
synteny_index(),
tau_index()
Examples
# Example using a permutation vector directly
# Suppose we want to sort the permutation p = c(1, 3, -2, 4)
inversionDistance(c(1, 3, -2, 4))
#> [1] 2
# Example using a GBreaks object.
# This example is based on Figure 4(a) from Hannehalli and Pevzner (1999).
# The inversion distance is 8.
inversionDistance(exampleInversionHP1999fig4a)
#> [1] 8