Partial Gene Orderings
Similar species will share many of the same genes, possibly with modifications. Thus, we can compare two genomes by analyzing the orderings of their genes, then inferring which rearrangements have separated the genes.
In “Enumerating Gene Orders”, we used permutations to model gene orderings. Yet two genomes will have evolved along their own separate paths, and so they won't share all of the same genes. As a result, we should modify the notion of permutation in order to quantify the notion of partial gene orderings.
A partial permutation is an ordering of only
Given: Positive integers
Return: The total number of partial permutations