Group-theoretic models of the inversion process in bacterial genomes

Attila Egri-Nagy, Volker Gebhardt, Mark M. Tanaka, Andrew R. Francis

    Research output: Contribution to journalArticlepeer-review

    22 Citations (Scopus)

    Abstract

    The variation in genome arrangements among bacterial taxa is largely due to the process of inversion. Recent studies indicate that not all inversions are equally probable, suggesting, for instance, that shorter inversions are more frequent than longer, and those that move the terminus of replication are less probable than those that do not. Current methods for establishing the inversion distance between two bacterial genomes are unable to incorporate such information. In this paper we suggest a group-theoretic framework that in principle can take these constraints into account. In particular, we show that by lifting the problem from circular permutations to the affine symmetric group, the inversion distance can be found in polynomial time for a model in which inversions are restricted to acting on two regions. This requires the proof of new results in group theory, and suggests a vein of new combinatorial problems concerning permutation groups on which group theorists will be needed to collaborate with biologists. We apply the new method to inferring distances and phylogenies for published Yersinia pestis data
    Original languageEnglish
    Pages (from-to)243-265
    Number of pages23
    JournalJournal of Mathematical Biology
    Volume69
    Issue number1
    DOIs
    Publication statusPublished - 2014

    Fingerprint

    Dive into the research topics of 'Group-theoretic models of the inversion process in bacterial genomes'. Together they form a unique fingerprint.

    Cite this