Please use this identifier to cite or link to this item: `http://repositorio.unicamp.br/jspui/handle/REPOSIP/321797`
DC FieldValueLanguage
dc.format.extent1 recurso online ( 137 p.) : il., digital, arquivo PDF.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languageInglêspt_BR
dc.relation.requiresRequisitos do sistema: Software para leitura de arquivo em PDFpt_BR
dc.typeTESE DIGITALpt_BR
dc.titleThe problem of sorting permutations by prefix and suffix rearrangements = O problema da ordenação de permutações usando rearranjos de prefixos e sufixospt_BR
dc.title.alternativeO problema da ordenação de permutações usando rearranjos de prefixos e sufixospt_BR
dc.contributor.authorLintzmayer, Carla Negri, 1990pt_BR
dc.contributor.nameofprogramPrograma de Pós-Graduação em Ciência da Computaçãopt_BR
dc.subjectRearranjo de genomaspt_BR
dc.subjectBiologia computacionalpt_BR
dc.subjectPermutações (Matemática)pt_BR
dc.subjectAlgoritmos de aproximaçãopt_BR
dc.subject.otherlanguageGenome rearrangementsen
dc.subject.otherlanguageComputational biologyen
dc.subject.otherlanguageSorting (Electronic computers)en
dc.subject.otherlanguagePermutationsen
dc.subject.otherlanguageApproximation algorithmsen
dc.description.abstractAbstract: The goal of the Pancake Flipping problem is to sort a stack of pancakes that have different sizes by performing as few operations as possible. The operation allowed is called prefix reversal and, when applied, flips the top of the stack of pancakes. Such problem is an interesting combinatorial problem by itself, but it has some applications in computational biology. Given two genomes that share the same genes and assuming that each gene appears only once per genome, we can represent them as permutations (stacks of pancakes are also represented by permutations). Then, we can compare the genomes by figuring out how one was transformed into the other through the application of genome rearrangements, which are large scale mutations. Reversals and transpositions are the most commonly studied types of genome rearrangements and a prefix reversal (or prefix transposition) is a type of reversal (or transposition) which is restricted to the beginning of the permutation. When the rearrangement is restricted to the end of the permutation, we say it is a suffix rearrangement. A problem of sorting permutations by rearrangements is, therefore, the problem to find a sequence of rearrangements with minimum cost that sorts a given permutation. The traditional approach considers that all rearrangements have the same unitary cost, in which case the goal is trying to find the minimum number of rearrangements that are needed to sort the permutation. Numerous efforts have been made over the past years regarding this approach. On the other hand, a long rearrangement (which is in fact a mutation) is more likely to disturb the organism. Therefore, weights based on the length of the segment involved may have an important role in the evolutionary process. We say this is the length-weighted approach and the goal is trying to find a sequence of rearrangements whose total cost (the sum of the cost of each rearrangement, which depends on its length) is minimum. In this thesis we present the first results regarding problems of sorting permutations by prefix and suffix reversals and transpositions considering both the traditional and the length-weighted approach. For the traditional approach, we considered a total of 10 problems and developed new results for 6 of them. For the length-weighted approach, we considered a total of 13 problems and developed new results for all of themen
dc.publisher[s.n.]pt_BR
dc.date.issued2016pt_BR
dc.identifier.citationLINTZMAYER, Carla Negri. The problem of sorting permutations by prefix and suffix rearrangements = O problema da ordenação de permutações usando rearranjos de prefixos e sufixos. 2016. 1 recurso online ( 137 p.). Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.pt_BR
dc.description.degreedisciplineCiência da Computaçãopt_BR
dc.description.degreenameDoutora em Ciência da Computaçãopt_BR
dc.contributor.committeepersonalnameFernandes, Cristina Gomespt_BR
dc.contributor.committeepersonalnameXavier, Eduardo Candidopt_BR
dc.contributor.committeepersonalnameUsberti, Fábio Luizpt_BR
dc.date.defense2016-12-15T00:00:00Zpt_BR
dc.date.available2017-04-20T17:20:22Z
dc.date.available2017-06-09T15:06:29Z-
dc.date.accessioned2017-04-20T17:20:22Z
dc.date.accessioned2017-06-09T15:06:29Z-
dc.description.provenanceMade available in DSpace on 2017-04-20T17:20:22Z (GMT). No. of bitstreams: 1 Lintzmayer, Carla Negri_D.pdf: 1656997 bytes, checksum: e5047f92ee628cb480d39e1071dacbe8 (MD5) Previous issue date: 2016en
dc.description.provenanceMade available in DSpace on 2017-06-09T15:06:29Z (GMT). No. of bitstreams: 1 Lintzmayer_CarlaNegri_D.pdf: 1656997 bytes, checksum: e5047f92ee628cb480d39e1071dacbe8 (MD5) Previous issue date: 2016en
dc.identifier.urihttp://repositorio.unicamp.br/jspui/handle/REPOSIP/321797