×

Sorting permutations and its application in genome analysis. (English) Zbl 0946.92018

Nehaniv, Chrystopher L., Mathematical and computational biology. Computational morphogenesis, hierarchical complexity, and digital evolution. An international workshop, University of Aizu, Aizu-Wakamatsu City, Japan, October 21-25, 1997. Providence, RI: AMS, American Mathematical Society. Lect. Math. Life Sci. 26, 191-201 (1999).
Summary: An efficient approach for checking the similarity between genomes on a large scale is to compare the order of appearance of identical genes in the two species. The two gene sequences differ not because of local mutations, but because of global rearrangements such as reversals, transpositions, and so on. Given the sequences of the identical genes of two species, if we express one sequence by \(I=(1,2,\dots,n)\) then the other sequence can be expressed by a permutation \(\pi=(\pi_1\pi_2,\dots,\pi_n)\) of \(\{1,2,\dots,n\}\). Checking the similarity between genomes based on general rearrangements leads to a combinatorical problem of finding a shortest series of rearrangements that sort the permutation \(\pi\) into the identity \(I\). We propose algorithms for permutation sorting by reversals and transpositions.
For the entire collection see [Zbl 0914.00107].

MSC:

92D20 Protein sequences, DNA sequences
92C40 Biochemistry, molecular biology
05A05 Permutations, words, matrices
68R05 Combinatorics in computer science
92-08 Computational methods for problems pertaining to biology
PDFBibTeX XMLCite