Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/321797
Full metadata record
DC FieldValueLanguage
dc.contributor.CRUESPUNIVERSIDADE ESTADUAL DE CAMPINASpt_BR
dc.descriptionOrientador: Zanoni Diaspt_BR
dc.descriptionTese (doutorado) - Universidade Estadual de Campinas, Instituto de Computaçãopt_BR
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.advisorDias, Zanoni, 1975-pt_BR
dc.contributor.institutionUniversidade Estadual de Campinas. Instituto de Computaçãopt_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.subjectOrdenação (Computadores)pt_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.abstractResumo: O Problema das Panquecas tem como objetivo ordenar uma pilha de panquecas que possuem tamanhos distintos realizando o menor número possível de operações. A operação permitida é chamada reversão de prefixo e, quando aplicada, inverte o topo da pilha de panquecas. Tal problema é interessante do ponto de vista combinatório por si só, mas ele também possui algumas aplicações em biologia computacional. Dados dois genomas que compartilham o mesmo número de genes, e assumindo que cada gene aparece apenas uma vez por genoma, podemos representá-los como permutações (pilhas de panquecas também são representadas por permutações). Então, podemos comparar os genomas tentando descobrir como um foi transformado no outro por meio da aplicação de rearranjos de genoma, que são eventos de mutação de grande escala. Reversões e transposições são os tipos mais comumente estudados de rearranjo de genomas e uma reversão de prefixo (ou transposição de prefixo) é um tipo de reversão (ou transposição) que é restrita ao início da permutação. Quando o rearranjo é restrito ao final da permutação, dizemos que ele é um rearranjo de sufixo. Um problema de ordenação de permutações por rearranjos é, portanto, o problema de encontrar uma sequência de rearranjos de custo mínimo que ordene a permutação dada. A abordagem tradicional considera que todos os rearranjos têm o mesmo custo unitário, de forma que o objetivo é tentar encontrar o menor número de rearranjos necessários para ordenar a permutação. Vários esforços foram feitos nos últimos anos considerando essa abordagem. Por outro lado, um rearranjo muito longo (que na verdade é uma mutação) tem mais probabilidade de perturbar o organismo. Portanto, pesos baseados no comprimento do segmento envolvido podem ter um papel importante no processo evolutivo. Dizemos que essa abordagem é ponderada por comprimento e o objetivo nela é tentar encontrar uma sequência de rearranjos cujo custo total (que é a soma do custo de cada rearranjo, que por sua vez depende de seu comprimento) seja mínimo. Nessa tese nós apresentamos os primeiros resultados que envolvem problemas de ordenação de permutações por reversões e transposições de prefixo e sufixo considerando ambas abordagens tradicional e ponderada por comprimento. Na abordagem tradicional, consideramos um total de 10 problemas e desenvolvemos novos resultados para 6 deles. Na abordagem ponderada por comprimento, consideramos um total de 13 problemas e desenvolvemos novos resultados para todos elespt
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.degreelevelDoutoradopt_BR
dc.description.degreedisciplineCiência da Computaçãopt_BR
dc.description.degreenameDoutora em Ciência da Computaçãopt_BR
dc.contributor.committeepersonalnameWalter, Maria Emilia Machado Tellespt_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.description.sponsordocumentnumber140017/2013-5pt_BR
dc.description.sponsordocumentnumber2013/01172-0pt_BR
dc.date.available2017-04-20T17:20:22Z-
dc.date.accessioned2017-04-20T17:20:22Z-
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.identifier.urihttp://repositorio.unicamp.br/jspui/handle/REPOSIP/321797-
dc.description.sponsorFAPESPpt_BR
dc.description.sponsorCNPQpt_BR
Appears in Collections:IC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Lintzmayer, Carla Negri_D.pdf1.62 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.