Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11567752_8 | T. Comp. Sys. Biology |
Keywords | Field | DocType |
gene sequence,coarse grain parallelism,polynomial-time approximation algorithm,fine grain,varying number,genomic distance,fine grain parallelism,intel c,coarse grain,smallest number,gene permutation,np hard problem,edit distance,genome evolution | Edit distance,Approximation algorithm,Computer science,Parallel computing,Permutation,Fine grain parallelism,Algorithm,Sorting,Compiler,Thread (computing) | Journal |
Volume | Issue | ISSN |
2 | null | 0302-9743 |
ISBN | Citations | PageRank |
3-540-29401-5 | 0 | 0.34 |
References | Authors | |
7 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vijaya Smitha Kolli | 1 | 0 | 0.68 |
| Hui Liu | 2 | 36 | 10.57 |
| Jieyue He | 3 | 128 | 18.92 |
| Michelle Hong Pan | 4 | 0 | 0.68 |
| Yi Pan | 5 | 2507 | 203.23 |