Name
Abstract | ||
|---|---|---|
Genome rearrangements are global mutations that change large stretches of DNA sequence throughout genomes. They are rare but accumulate during the evolutionary process leading to organisms with similar genetic material in different places and orientations within the genome. Sorting by Genome Rearrangements problems seek for minimum-length sequences of rearrangements that transform one genome into the other. These problems accept alternative versions that assign weights for each event, and the goal is to find a minimum-weight sequence. We study the Sorting by Weighted Reversals and Transpositions problem on signed permutations. In this study, we use weight 2 for reversals and 3 for transpositions and consider theoretical and practical aspects in our analysis. We present two algorithms with approximation factors of 5/3 and 3/2. We also developed a generic approximation algorithm to deal with different weights for reversals and transpositions, and we show the approximation factor reached in each scenario. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1089/cmb.2018.0257 | JOURNAL OF COMPUTATIONAL BIOLOGY |
Keywords | Field | DocType |
approximation algorithms,genome rearrangement,reversals,transpositions,weighted operations | Genome,Approximation algorithm,Genome rearrangement,Sorting,DNA sequencing,Artificial intelligence,Computational biology,Machine learning,Mathematics | Conference |
Volume | Issue | ISSN |
26.0 | 5 | 1066-5277 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andre Rodrigues Oliveira | 1 | 0 | 6.76 |
| Klairton Lima Brito | 2 | 0 | 1.01 |
| Zanoni Dias | 3 | 262 | 44.40 |
| Ulisses Dias | 4 | 41 | 13.23 |