Calculating Genomic Distances in Parallel Using OpenMP

  • Vijaya Smitha Kolli
  • Hui Liu
  • Jieyue He
  • Michelle Hong Pan
  • Yi Pan
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3680)


By finding the corresponding shortest edit distance between two signed gene permutations, we can know the smallest number of insertions, deletions, and inversions required to change on string of genes into another, where insertion, deletion and inversion are the process of genome evolutions. However, it is NP-hard problem to compute the edit distance between two genomes. Marron et al proposed a polynomial-time approximation algorithm to compute (near) minimum edit distances under inversions, deletions, and unrestricted insertions. Our work is based on Marron’s et al algorithm, which carries out lots of comparisons and sorting to calculate the edit distance. These comparisons and sorting are extremely time-consuming, and they result in the decrease of the efficiency. We believe the efficiency of the algorithm can be improved by parallelizing. We parallelize their algorithm via OpenMP on Intel C++ compiler for Linux 7.1, and compare three levels of parallelism: coarse grain, fine grain and combination of both. The experiments are conducted for a varying number of threads and length of the gene sequences. The experimental results have shown that either coarse grain parallelism or fine grain parallelism alone does not improve the performance of the algorithm very much, however, the combination of both fine grain and coarse grain parallelism have improve the performance to a great extent.


Edit Distance Chunk Size Genomic Distance Edit Sequence OpenMP Program 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bader, D.A., Moret, B.M.E., Yan, M.: A Fast Linear-time Algorithm for Inversion Distance with an Experimental Comparison. J. Comput. Biol. 8(5), 483–491 (2001)CrossRefGoogle Scholar
  2. 2.
    Marron, M., Sweson, K.M., Moret, B.M.E.: Genomic Distances under Deletions and Insertions. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 537–547. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  3. 3.
    Caprara, A.: Sorting by Reversals is Difficult. In: Proc. 1st Int’l Conf. on Comput. Mol. Biol. RECOMB 1997, pp. 75–83. ACM Press, New York (1997)CrossRefGoogle Scholar
  4. 4.
    Hannenhalli, S., Pevzner, P.: Transforming Cabbage into Turnip (Polynomial Algorithm for Sorting Signed Permutations by Reversals). In: Proc. 27th Ann.Symp. Theory of Computing STOC 1995, pp. 178–189. ACM Press, New York (1995)CrossRefGoogle Scholar
  5. 5.
    El-Mabrouk, N.: Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol. 1848, pp. 222–234. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  6. 6.
    Liu, T., Moret, B.M.E., Bader, D.A.: An Exact Linear-time Algorithm for Computing Genomic Distances under Inversions and Deletions U. New Mexico, TR-CS-2003-31Google Scholar
  7. 7.
  8. 8.
    Quinn, M.: Parallel Programming in C with MPI and OpenMP. The McGraw-Hill Companies, New York (2004)Google Scholar
  9. 9.
  10. 10.
    Kaplan, H., Shamir, R., Tarjan, R.E.: Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. In: Proc. SODA 1997, pp. 344–351 (1997); SIAM Journal on Computing 29(3), 880–892 (1999)Google Scholar
  11. 11.
    Hwang, K.: Advanced Computer Architecture – Parallelism, Scalability, Programmability. McGraw-Hill, New York (1993)Google Scholar
  12. 12.
    Tian, X., Bik, A., Girkar, M., Grey, P., Satio, H., Su, E.: Intel OpenMP C++/Fortran Compiler for Hyper-Threading Technology: Implementation and Performance. Intel TechnologyJourna (February 2002),
  13. 13.
    Dobzhansky, T., sturtevant, A.H.: Inversions in the Chromosome of Drosophila Pseudoobscura. Genetics 23, 28–64 (1938)Google Scholar
  14. 14.
    Bryant, D.: The Complexity of Calculating Exemplar Distances. In: Sankoff, D., Nadeau, J. (eds.) Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families, pp. 207–212. Kluwer Academic Pubs., Dordrecht (2000)Google Scholar
  15. 15.
    Sankoff, D.: Genome Rearrangement with Gene Families. Bioinformatics 15(11), 909–917 (1999)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Vijaya Smitha Kolli
    • 1
  • Hui Liu
    • 1
  • Jieyue He
    • 1
    • 2
  • Michelle Hong Pan
    • 3
  • Yi Pan
    • 1
  1. 1.Department of Computer ScienceGeorgia State UniversityAtlantaUSA
  2. 2.Department of Computer ScienceSoutheast UniversityNanjing, JiangsuChina
  3. 3.Centers for Disease Control and Prevention, Office of Workforce and Career Development, Career Development Division, Public Health Informatics Fellow ProgramAtlantaUSA

Personalised recommendations