The week's pick
Reseach Article
Parallel Algorithm for Sorting a Signed Permutation by Reversals on MOT Interconnection Netwo
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 1 - Number 10 |
| Year of Publication: 2010 |
| Authors: Amritanjali, G. Sahoo |
10.5120/214-363
|
Amritanjali, G. Sahoo . Parallel Algorithm for Sorting a Signed Permutation by Reversals on MOT Interconnection Netwo. International Journal of Computer Applications. 1, 10 ( February 2010), 99-103. DOI=10.5120/214-363
Abstract
The problem of sorting a signed permutation by reversals is inspired and motivated by comparative genomics. Following the first polynomial time solution of this problem, several improvements have been published on the subject. The currently fastest algorithms is defined by the sequence augmentation sorting algorithm using balanced binary tree with running time O(n3/2√log n). We give a parallel implementation of the sequence augmentation sorting algorithm on the Mesh of trees architecture.
References
- Arslan, A. N. 2006. An algorithm for string edit distance allowing substring reversals. Sixth IEEE Symposium on BionInformatics and BioEngineering.
- Bader, D. A., Moret, B. M. E., Yan, M. 2001. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. In Proceedings of the Workshop on Algorithms and Data Structures, 2001, pp. 365–376.
- Bader, M., Abouelhoda, M., Ohlebusch, E. 2008. A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions. BioMed Central Bioinformatics .
- Chen, W., Chen, G., Hsu, D. F. 2000. Combinatorial properties of Mesh of Trees. In Proceedings of the International Symposium on Architectures, Algorithms and Networks, 134-139.
- Diekmann, Y., Sagot, M., and Tannier, E. 2007. Evolution under Reversals : Parsimony and Conservetion of Common Intervals. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 4, No. 2.
- Hannenhalli, S., Pevzner, P. 1999. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). J. Assoc. Comput. Mach. 46 (1999) 1–27.
- Kaplan, H., Verbin, E. 2003. Efficient data structures and a new randomized approach for sorting signed per mutations by reversals. In Proceedings of the CPM’03, Lecture Notes in Computer Science, vol. 2676, Springer, Berlin, 170–185.
- Li, Z., Wang, L. and Zhang, K. 2006. Algorithmic Approaches for Genome Rearrangement: A Review. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 36.
- Roy, S., Rahman, M., and Thakur, A. K. 2008. Sorting Primitives and Genome Rearrangement in Bioinformatics: A Unified Perspective. In Proceedings of World Academy of Science, Engineering and Technology, Vol. 28.
- Tannier, E., Bergeron, A., Sagot, M. F. 2007. Advances on sorting by reversals. Applied Discrete Mathematics Elsevier (2007), 881– 888.
Index Terms
Keywords