Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Length-weighted lambda-rearrangement distance

Texto completo
Autor(es):
Alexandrino, Alexsandro Oliveira [1] ; Miranda, Guilherme Henrique Santos [1] ; Lintzmayer, Carla Negri [2] ; Dias, Zanoni [1]
Número total de Autores: 4
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
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 41, n. 3 NOV 2020.
Citações Web of Science: 0
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
Linha de fomento: Auxílio à Pesquisa - Regular
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
Linha de fomento: Auxílio à Pesquisa - Temático
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
Linha de fomento: Auxílio à Pesquisa - Temático