Sorting Primitives and Genome Rearrangementin Bioinformatics: A Unified Perspective

Authors: Swapnoneel Roy, Minhazur Rahman, Ashok Kumar Thakur

Abstract:

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.

Keywords: Sorting Primitives, Genome Rearrangements, Transpositions, Block Interchanges, Strip Exchanges.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1055515

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.