Name
Title | ||
|---|---|---|
An efficient algorithm for computing non-overlapping inversion and transposition distance. |
Abstract | ||
|---|---|---|
Given two strings of the same length n, the non-overlapping inversion and transposition distance (also called mutation distance) between them is defined as the minimum number of non-overlapping inversion and transposition operations used to transform one string into the other. In this study, we present an O ( n 3 ) time and O ( n 2 ) space algorithm to compute the mutation distance of two input strings. An efficient algorithm for computing non-overlapping inversion and transposition distance is proposed.The lengths of two adjacent and non-overlapping fragments exchanged by a transposition can be different.The algorithm has useful applications to evolutionary tree constructions. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ipl.2016.07.004 | Information Processing Letters |
Keywords | Field | DocType |
Algorithms,Computational biology,Inversion,Transposition,Mutation distance | Transposition (music),Discrete mathematics,Combinatorics,Phylogenetic tree,Inversion (meteorology),Algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
116 | 12 | 0020-0190 |
Citations | PageRank | References |
2 | 0.43 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toan Thang Ta | 1 | 2 | 1.44 |
| Cheng-Yao Lin | 2 | 2 | 0.76 |
| Chin Lung Lu | 3 | 423 | 34.59 |