Name
Title | ||
|---|---|---|
Two-string consensus problem under non-overlapping inversion and transposition distance. |
Abstract | ||
|---|---|---|
For biological sequences that can be represented as strings over a finite alphabet, inversion and transposition are commonly observed mutation operations. The non-overlapping inversion and transposition distance (also simply called mutation distance) between two strings is defined as the minimum number of non-overlapping inversion and transposition operations used to transform one string into the other. Given two strings of the same length n and a constant c≥0, the two-string consensus problem under mutation distance is to determine whether or not there exists a string s⁎ such that the mutation distance from s⁎ to each input string does not exceed c. In this study, we present an O(n5) time and O(n4) space algorithm to solve this problem. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ipl.2017.10.006 | Information Processing Letters |
Keywords | Field | DocType |
Algorithms,Computational biology,Two-string consensus problem,Inversion,Transposition | Consensus,String searching algorithm,Discrete mathematics,Transposition (music),Combinatorics,Existential quantification,Inversion (meteorology),Damerau–Levenshtein distance,Approximate string matching,Mathematics,Alphabet | Journal |
Volume | Issue | ISSN |
130 | C | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 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 |