Probability and counting methods for approximate genome median arrangements
Counting approximate breakpoint medians of random genomes
Computational Engineering, Finance, and ScienceData Structures and Algorithms
Summary
The paper looks at how to find a genome arrangement that is close to several other genomes by counting how many pairs of genes are consecutive or not. Because finding the exact best genome that fits all given genomes is very hard, the authors introduce a way to count genomes that are approximately close enough, making the problem easier to understand and solve. They calculate the likelihood that a random genome is a good approximate fit and also estimate how many exact best-fit genomes there might be. This method helps in understanding genome similarities when exact solutions are too complex.
What this means in practice
- •For bioinformatics developers: Compute probable approximate median genomes quickly to aid genome comparison tools when exact medians are computationally infeasible.
- •For computational genomics teams: Model probabilities of approximate genome consensus to improve methods for reconstructing ancestral genomes or evolutionary pathways.
Authors
Poly H. da Silva, Arash Jamshidpey, David Sankoff
Abstract
Unsigned linear unichromosomal genomes with genes labeled 1, . . . , n are represented by permutations of these labels, whose adjacencies are the unordered pairs of genes occurring consecutively. The breakpoint distance counts the adjacencies of one genome that are absent from the other, and a breakpoint median minimizes the total breakpoint distance to a given set of genomes. Deciding whether a permutation is a median often requires a minimization over the whole symmetric group, which makes the median set resistant to exact counting. We replace this global condition by a local one: a c-approximate median is a genome having at most c adjacencies absent from all the input genomes. For a fixed genome we introduce its approximate median inverse, the set of ordered k-tuples of genomes ad- mitting it as a c-approximate median, and we construct and count this set explicitly. For k genomes chosen uniformly and independently at random, this gives the probability that a given genome is a c-approximate median and the expected number of such approximate medians. The relaxation is not only technical: approximate medians and near-optimal genomes co- incide up to a shift of the tolerance that remains bounded in probability as the number of genes grows. Finally, we derive an explicit upper bound on the probability that a given genome is an exact median, and on the expected number of exact breakpoint medians.