Generalizações de problemas envolvendo partição de strings

Resumo

O problema de partição comum mínima de strings é um problema de otimização combinatória com grande relevância tanto pelo seu aspecto teórico quanto prático. Esse problema tem como objetivo encontrar o número mínimo de substrings necessárias para formar duas strings distintas dadas como entrada, mudando apenas a ordem em que as substrings são concatenadas. Várias relações foram estabelecidas entre suas variações e problemas de rearranjo de genomas, os quais são importantes para comparação genômica. Em estudos mais recentes, os problemas de rearranjo vêm incorporando informações sobre as regiões intergênicas, o que motiva a incorporação dessas estruturas também nos problemas de partição. Além disso, a maior parte dos resultados conhecidos para os problemas de partição assumem que as duas strings consideradas no problema são formadas pelos mesmos caracteres, mas existe uma versão mais geral do problema que permite strings com um conjunto distinto de caracteres, ou seja, onde existem caracteres presentes em apenas uma das strings. O objetivo deste trabalho é estudar variações do problema de partição comum mínima de strings, incluindo generalização que envolvem a adição de informação sobre as regiões intergênicas e a presença de caracteres em apenas uma das strings. (AU)