Full text  
Author(s): 
Total Authors: 3

Affiliation:  ^{[1]} Univ Estadual Campinas, Inst Comp, Campinas, SP  Brazil
^{[2]} Univ Nantes, UMR CNRS 6004, LS2N, Nantes  France
Total Affiliations: 2

Document type:  Journal article 
Source:  THEORETICAL COMPUTER SCIENCE; v. 715, p. 3559, MAR 8 2018. 
Web of Science Citations:  0 
Abstract  
Comparative genomics is a line of study which aims at determining dis/similarities between genomes. One way of doing this is to infer the large scale mutations (also called genome rearrangements) that are responsible for transforming one genome into another, under the parsimony principle. Numerous efforts have been made over the past years regarding the traditional approach, in which all genome rearrangements have the same unit cost. However, since long rearrangements are more likely to disturb the organism, some works considered the lengthweighted approach, in which the cost of each rearrangement is a function of its length. The problem is thus modeled as follows: given two genomes G(1) and G(2) and a set beta of allowed genome rearrangements, each with a given cost, determine their distance, i.e., the total cost of a minimumcost sequence of rearrangements from beta that transforms G(1) into G(2). In this paper, we study lengthweighted reversals and transpositions, mainly considering their prefix variants (in which the leftmost part of the genome must always be included). We present approximation algorithms and bounds on the distances and diameters (i.e., maximum possible distance over any two genomes of same length) for eight problems when genomes are represented as permutations, and another eight problems when genomes are represented as binary strings, in each case considering two different cost functions. (C) 2018 Elsevier B.V. All rights reserved. (AU)  
FAPESP's process:  14/207387  Sorting permutations by prefix reversals and suffix reversals 
Grantee:  Carla Negri Lintzmayer 
Support type:  Scholarships abroad  Research Internship  Doctorate (Direct) 
FAPESP's process:  14/194018  Genome rearrangement algorithms 
Grantee:  Zanoni Dias 
Support type:  Regular Research Grants 
FAPESP's process:  13/011720  The sorting permutations problem using prefix and suffix operations 
Grantee:  Carla Negri Lintzmayer 
Support type:  Scholarships in Brazil  Doctorate (Direct) 
FAPESP's process:  15/119379  Investigation of hard problems from the algorithmic and structural stand points 
Grantee:  Flávio Keidi Miyazawa 
Support type:  Research Projects  Thematic Grants 
FAPESP's process:  13/082937  CCES  Center for Computational Engineering and Sciences 
Grantee:  Munir Salomao Skaf 
Support type:  Research Grants  Research, Innovation and Dissemination Centers  RIDC 