Length-weighted $$\lambda $$ λ -rearrangement distance

Alexsandro Oliveira Alexandrino (), Guilherme Henrique Santos Miranda (), Carla Negri Lintzmayer () and Zanoni Dias ()
Additional contact information
Alexsandro Oliveira Alexandrino: University of Campinas
Guilherme Henrique Santos Miranda: University of Campinas
Carla Negri Lintzmayer: Federal University of ABC
Zanoni Dias: University of Campinas

Journal of Combinatorial Optimization, 2021, vol. 41, issue 3, No 1, 579-602

Abstract: Abstract Comparative genomics is a field of biology that aims at comparing genomes of different species. One major question of this field is to find the evolutionary distance between two given genomes. One way to estimate such distance is to use the rearrangement distance, which consists in finding a minimum cost sequence of rearrangements that transforms one genome into another. We use permutations to model the genomes being compared and, in this way, we can treat this problem as the problem of sorting a permutation with a minimum cost sequence of rearrangements. In the early works with rearrangement distance, it was considered that all rearrangements are equally likely to occur and, consequently, they use a unitary cost for all rearrangements. Some variations of the problem were motivated by the observation that rearrangements involving large segments of a genome rarely occur. One of these variants also uses a unitary cost, however it adds a constraint in the length of the operations allowed to estimate the distance. Another variant uses a cost function based on the rearrangement’s length. In this work, we study problems that combine both variants, that is, problems with a constraint in the rearrangement’s length and with a cost function based on the rearrangement’s length. We present approximation algorithms for five such problems involving reversals and/or transpositions for sorting signed and unsigned permutations. We also analyze the problems for specific parameters of the length restriction and for when the cost function is equal to $$\ell ^\alpha $$ ℓ α , where $$\ell $$ ℓ is the rearrangement’s length and $$\alpha \ge 1$$ α ≥ 1 is a real value parameter.

Keywords: Genome rearrangements; Approximation algorithms; Sorting permutations (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00673-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:3:d:10.1007_s10878-020-00673-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00673-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().