Length-weighted lambda-rearrangement distance

Autor(es)

Alexandrino, Alexsandro Oliveira ^[1] ; Miranda, Guilherme Henrique Santos ^[1] ; Lintzmayer, Carla Negri ^[2] ; Dias, Zanoni ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil

^[2] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 41, n. 3, p. 579-602, APR 2021.
• Citações Web of Science: 1

Resumo

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 l(alpha), where l is the rearrangement's length and alpha >= 1 is a real value parameter. (AU)

• Processo FAPESP: 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo
• Beneficiário: Sandra Eliza Fontes de Avila
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade
• Beneficiário: Anderson de Rezende Rocha
• Modalidade de apoio: Auxílio à Pesquisa - Temático