Sorting Primitives and Genome Rearrangementin Bioinformatics: A Unified Perspective

Bioinformatics and computational biology involve the use of techniques including applied mathematics, informatics, statistics, computer science, artificial intelligence, chemistry, and biochemistry to solve biological problems usually on the molecular level. Research in computational biology often overlaps with systems biology. Major research efforts in the field include sequence alignment, gene finding, genome assembly, protein structure alignment, protein structure prediction, prediction of gene expression and proteinprotein interactions, and the modeling of evolution. Various global rearrangements of permutations, such as reversals and transpositions,have recently become of interest because of their applications in computational molecular biology. A reversal is an operation that reverses the order of a substring of a permutation. A transposition is an operation that swaps two adjacent substrings of a permutation. The problem of determining the smallest number of reversals required to transform a given permutation into the identity permutation is called sorting by reversals. Similar problems can be defined for transpositions and other global rearrangements. In this work we perform a study about some genome rearrangement primitives. We show how a genome is modelled by a permutation, introduce some of the existing primitives and the lower and upper bounds on them. We then provide a comparison of the introduced primitives.

Authors:

• Swapnoneel Roy
• Minhazur Rahman
• Ashok Kumar Thakur

Keywords:

• Sorting Primitives
• Genome Rearrangements
• Transpositions
• Block Interchanges
• Strip Exchanges.

References:

[1] M. Mahajan, R.Rama, V. Raman, and S. Vijaykumar. Approximate
block sorting. International Journal of Foundation of
Computer Science,17(2):337-355, 2006.
[2] M. Mahajan, R. Rama, V. Raman, and S. Vijayakumar.
Merging and sorting by block moves. In Proc. of the 23rd
Conference on Foundations of Software Technology and Theoretical
Computer Science, FSTTCS 2003, LNCS vol. 2914,
pages 314 - 325. Springer-Verlag, Dec 2003.
[3] P. Pevzner. Computational Molecular Biology: An Algorithmic
Approach. MIT Press, Cambridge, MA, USA, 2000.
[4] V.Bafna and P.Pevzner. Genome rearrangements and sorting
by reversals. SIAM Journal on Computing, 25:272-289, 1996.
[5] V. Bafna and P. Pevzner. Sorting by transpositions. SIAM
Journal on Discrete Mathematics 11(2):224-240, may 1998.
[6] W.W. Bein, L.L. Larmore, L. Morales, and I.H. Sudborough.
A Polymomial Time 2-Approximation for Block Sorting. In
Proc. of the 15th Annual Symposium on Fundamentals of
Computing Theory, FCT 2005, August 2005, LNCS 3623,
pages 115-124, Springer-Verlag, August 2005.
[7] David Alan Christie. Genome Rearrangement Problems. PhD
thesis, The University of Glasgow, Glasgow,UK, August 1998.
[8] G.H Lin and G Xue. Signed genome arrangement by reversals
and transpositions: Models and approximations. Theoretical
Computer Science, 259:513-531, 2001.
[9] S. Hannenhalli and P. Pevzner. Transforming cabbage into
turnip: Polynomial algorithm for sorting signed permutations
by reversals. Journal of the ACM, 46:1-27, 1999.
[10] T. Hartman. A simpler 1.5-approximation algorithm for sorting
by transpositions. In Combinatorial Pattern Matching
(CPM 03), 2676:156169, 2003.
[11] Swapnoneel Roy, Ashok Kumar Thakur, Anupama Pande,
Minhazur Rahman, Algorithms and Design for an Autonomous
Biological System, icas, p. 35, Third International
Conference on Autonomic and Autonomous Systems
(ICAS-07), 2007
[12] A. Bergeron, J. Mixtacki, J. Stoye. A unifying view of genome
rearrangements. PICB Spring School, Shanghai, March 12-16,
2007
[13] Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Bioinformatics.
[14] Swapnoneel Roy, Amitabh Bhattacharya. Algorithms for Sorting
using Genomically Motivated Primitives. In Proc. of
National Conference on Methods and Models in Computing
(NCM2C-2007), JNU, New Delhi, India.