Parallel Algorithm for Sorting a Signed Permutation by Reversals on MOT Interconnection Network
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 has 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). the authors give a parallel implementation of the sequence augmentation sorting algorithm on the Mesh of trees architecture. With new techniques for sequencing the entire genome of organisms, biology is rapidly moving towards a data-intensive computational science.