Name
Abstract | ||
|---|---|---|
In computational biology, genome rearrangements is a field in which we study mutational events affecting large portions of a genome. One such event is the transposition, that changes the position of contiguous blocks of genes inside a chromosome. This event generates the problem of transposition distance, that is to find the minimal number of transpositions transforming one chromosome into another. It is not known whether this problem is $\mathcal{NP}$-hard or has a polynomial time algorithm. Some approximation algorithms have been proposed in the literature, whose proofs are based on exhaustive analysis of graphical properties of suitable cycle graphs. In this paper, we follow a different, more formal approach to the problem, and present a 1.5-approximation algorithm using an algebraic formalism. Besides showing the feasibility of the approach, the presented algorithm exhibits good results, as our experiments show. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-85557-6_11 | BSB |
Keywords | Field | DocType |
computational biology | Genome,Transposition (music),Approximation algorithm,Discrete mathematics,Graph,Combinatorics,Algebraic number,Mathematical proof,Formalism (philosophy),Bioinformatics,Time complexity,Mathematics | Conference |
Volume | ISSN | Citations |
5167 | 0302-9743 | 2 |
PageRank | References | Authors |
0.46 | 10 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cleber V. G. Mira | 1 | 2 | 0.46 |
| Zanoni Dias | 2 | 262 | 44.40 |
| Hederson P. Santos | 3 | 2 | 0.46 |
| Guilherme A. Pinto | 4 | 6 | 1.63 |
| Maria Emilia M. T. Walter | 5 | 37 | 14.23 |