ARAUJO, Samuel Nascimento de. Número de dominação romana em grafos. 2016. 51 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-25T17:42:43Z No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2017-01-26T20:23:42Z (GMT) No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) / Made available in DSpace on 2017-01-26T20:23:42Z (GMT). No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) Previous issue date: 2016 / In a Roman domination of a graph, vertices are assigned a value from {0,1,2} in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. In this dissertation, we show the history of the problem and prove that the Roman domination number is NP-Complete even for induced subgraphs of grids and it is APX-hard even for bipartite graphs with maximum degree 4. We also prove that the Roman domination number is fixed parameter tractable for graphs with bounded local treewidth, as graphs with bounded maximum degree or bounded genus (like planar graphs or toroidal graphs). We also obtain complexity results when we consider digraphs as an input for the problem such as bipartite tournaments and planar digraphs. / No problema de dominação romana de um grafo, os vértices são atribuídos um valor de {0,1,2}, de tal maneira que cada vértice atribuído o valor 0 é adjacente a um vértice que foi atribuído o valor 2. O número de dominação romana é a menor soma possível de todos os valores dos vértices em tal atribuição. Nesta dissertação apresentamos a história do problema, e provamos que o número dominação romana é NP-Completo mesmo para subgrafos induzidos de grids e é APX-difícil mesmo para grafos bipartidos com o grau máximo 4. Nós também provamos que o número de dominação romana é tratável por parâmetro fixo para grafos com treewidth local limitada, como grafos com grau máximo limitado ou genus limitado (como por exemplo grafos planares). Nós também obtivemos resultados de complexidade quando consideramos digrafos como entrada para o problema, tais como torneios bipartidos e digrafos planares.

Esta dissertação resultou de um sistema computacional voltado para a visualização gráfica de análises comparativas entre genomas de procariotos. O sistema denominado de GINGA Graphical Interface for comparative Genome Analysis foi desenvolvido basicamente para analisar genomas parcialmente seqüenciados por meio da comparação com genomas completos. O sistema mostra a representação do alinhamento entre seqüências de reads, contigs e scaffolds do genoma parcial com a seqüência completa do outro genoma, permitindo a identificação de blocos comuns, regiões específicas e rearranjos. GINGA é um sistema web-based que foi desenvolvido em linguagem PERL para acessar um banco de dados MySQL, onde estão armazenadas as informações obtidas nas análises comparativas. O módulo de interface da biblioteca gráfica GD da linguagem PERL foi utilizado para a construção da ferramenta de visualização. A representação gráfica criada permite a navegação com opções de zoom in/out, disponibilizando as informações de montagem, anotação das seqüências codificadoras e da organização das seqüências entre os genomas. Relatórios são ainda disponibilizados como fonte complementar da apresentação dos resultados. O sistema GINGA foi utilizado para analisar de maneira comparativa o genoma das bactérias Leifsonia xyli subsp. cynodontis (Lxc genoma parcialmente seqüenciado) e Leifsonia xyli subsp. xyli (Lxx genoma completamente seqüenciado). Lxx provoca o raquitismo da soqueria em cana-de-açúcar, enquanto Lxc é capaz de colonizar cana-de-açúcar sem provocar sintomas de doença. O objetivo foi revelar, ainda durante o processo de seqüenciamento do genoma de Lxc, diferenças genéticas existentes entre os genomas dessas duas bactérias. Fizeram parte das análises comparativas um total de 9.754 reads do genoma de Lxc que formaram 1.064 contigs e 317 scaffolds, totalizando 1.470.731 de bases não redundantes. GINGA permitiu a identificação de 206.320 bases (~19%) em seqüências de contigs específicos (contigs que não apresentaram alinhamento algum com o genoma completo de Lxx) e 19 scaffolds (5,9%) que totalizaram 56.884 bases específicas ao genoma de Lxc, além de aproximadamente 1 milhão de nucleotídeos alinhados ao genoma de Lxx e pelo menos 6 grandes rearranjos. Estes resultados foram disponibilizados em uma interface gráfica e relatórios, permitindo orientar o andamento do projeto de seqüenciamento do genoma de Lxc quanto à seleção das regiões a serem seqüenciadas e, simultaneamente, oferecendo informações para a formalização de hipóteses relevantes à biologia destes microorganismos. / This study aimed to develop a computational system applied to the comparative analysis of prokaryotic genomes in a graphical view. The system named GINGA Graphical Interface for comparative Genome Analysis was developed to analyse a draft genome sequence in comparison to a complete genome. The system shows the alignment between sequence of reads, contigs and scaffolds from partial sequenced genomes and the complete sequence of another genome and allows the identification shared and unique regions as well as rearrangements. GINGA is a web-based system developed using the PERL language to access a MySQL database where all the information regard to the comparative analysis is stored. The module of the interface to GD (Graphics Library) was used to help the construction of the graphical tool. The graphical view allows zoom in/out on the information on assembly, annotation and the organization of the sequences. Supplementary information can be accessed in the form of reports. GINGA system was used to compare the genomes of Leifsonia xyli subsp. cynodontis (Lxc draft genome sequence) and Leifsonia xyli subsp. xyli (Lxx complete genome sequence). The mail goal was to identify genetic differences that may help to understand the pathogeniciy of Lxx towards sugarcane. A total of 9.754 reads assembled in 1.064 contigs and 317 scaffolds produced 1.470.731 of no redundant bases of Lxc genome and were used in the analysis. GINGA allowed the identification of 206.320 bp (~20%) of Lxc specific sequences organized in contigs and 56.884 bp organized in 19 scaffolds (5,9%), around 1 milion bp aligned to Lxx genome and at least 6 large scale genomic rearrangements. These results were presented in a graphical interface and allowed to guide the partial genome sequencing, helping to decide which regions should be further sequenced and at the same time allowing the formulation of hypothesis related to important biological aspects of these microorganisms

Discernir as relações evolutivas entre os grandes grupos animais tem representado um formidável desafio para a Ciência. Os filos animais possuem arquiteturas corporais bastante distintas e por isso difíceis de serem comparadas. Ao mesmo tempo, seu registro fóssil converge aproximadamente para um mesmo intervalo na escala geológica, dificultando uma reconstrução filogenética com caracteres morfológicos. A disponibilidade de dados moleculares sobre os organismos abriu, contudo, novas possibilidades na filogenia animal. Esta dissertação buscou explorar essas possibilidades inferindo uma filogenia com métodos de distância e máxima verossimilhança, a partir de todos os genomas mitocondriais, completamente seqüenciados até o momento. No entanto, apenas alguns grandes agrupamentos como Diploblastica, Bilateria, Deuterostomia e Protostomia foram recuperados com forte suporte estatístico, além de pequenos agrupamentos de animais de mesma ordem ou família, indicando que os efeitos da rápida radiação no Cambriano se estenderam também ao registro molecular. Os resultados também indicam a necessidade de buscar modelos de evolução mais aderentes a este cenário. Deuterostomia, por exemplo, só foi recuperado monofileticamente assumindo-se a distribuição gama para variabilidade entre-sítios, ao custo, entretanto, da perda de definição nos ramos menores. Nematóides e Platelmintos, por sua vez, revelam um possível viés no skew (desvio) do conteúdo GC e AT de seus genes mitocondriais, que não é adequadamente mapeado por modelos de substituição reversíveis. Os indícios são de que a resolução da filogenia animal depende ainda de uma melhor compreensão da evolução molecular em escala genômica. / Inferring the evolutive relations between the animal phyla has been a formidable challenge to Science. The animal phyla represent quite distinct baupläne (body architectures) and are, therefore, difficult to compare. At the same time, their fossil record converges mostly to the same period on the geological scale. The recent availability of molecular data has, however, inaugurated a new front in animal phylogeny. The present work explores this opportunity by inferring a phylogeny with distance and maximum likelihood methods, employing all animal mitochondrial genomes ever sequenced. The results present only a few bigger groups with strong statistical support, like Diploblastica, Bilasteria, Protostomia and Deutorostomia, and many smaller groups of animals belonging to the same order or family. These results seems to confirm that the phyla radiated in such a short time interval that the phylogenetic signal did not hold out to produce a satisfactory resolution of the animal tree to date. Some limits may have yet to be tested, through models of evolution more fit to this scenario. For example was only recovered with the use of gamma distances for site-to-site substitution rate variability, at the expense of compressing the smaller branches throughout the tree. Nematodes and Platyhelminthes reveal a bias in GC and AT skew that cannot be adequately mapped by any reversible substitution pattern. Nevertheless, even if corrections are found for these issues, it is well possible that the hope of a better resolution in the animal tree will lie further on, by a better understanding of the evolutive process in a genomic scale.

O uso da tecnologia da informação na implementação de bases de dados com informações sobre a biodiversidade, vem ganhando uma grande importância. Isso se deve a grande necessidade de se promover um acesso livre a dados e informações sobre as espécies. O acesso a essas informações é considerado como fundamental para o desenvolvimento de diferentes áreas do conhecimento. A presente dissertação teve como objetivo o desenvolvimento de um sistema computacional para acesso a informações sobre a biodiversidade do Estado do Rio de Janeiro. O sistema Biota-Rio deverá conter informações sobre as espécies de animais, vertebrados e invertebrados, que foram descritas para o Estado do Rio de Janeiro. Informações como descrições originais, localidades-tipo, ambiente e outras informações estarão disponíveis no sistema. Biota-Rio é um sistema de acesso livre via web, que foi implementado utilizando a linguagem de programação PERL. O MySQL foi o SGBD utilizado na implementação do banco de dados onde estarão depositadas as informações sobre as espécies. Até o momento, foram feitos levantamentos das referências para trinta e seis espécies de mamíferos utilizando a base de dados Zoological Record. / The use of information technology in biodiversity related databases is increasing due to the open access to a large sum of data. Access to this information may be regarded as crucial to different areas of knowledge. The present work aims at the development of a open access computational system on biodiversity of the State of Rio de Janeiro. The Biota-Rio system focuses on the animal species, vertebrates and invertebrates, which were originally described for the State of Rio de Janeiro. In this sense, key information such as original descriptions, type localities, habitats and other are directly available on the system. Biota-Rio is a system in which the user may freely access the information via web that was implemented using the PERL language. The MySQL was the selected DBMS in the implementation of the database in which the informations are deposited. To date, surveys have been made of references to thirty-six species of mammals using the Zoological Record database.

Nesta tese apresenta-se uma nova formulação mista estabilizada regularizada de elementos finitos nas variáveis primais com interpolação contínua para a velocidade e descontínua para a pressão, para problemas de fluidos viscoplásticos.Esta formulação tem base nos métodos de lagrangeano aumentado-regularização e de estabilização por mínimos quadrados.Discutem-se as dificuldades de resolução dos problemas viscoplásticos especialmente aqueles modelados pela relação de Bingham que prevê uma descontinuidade na forma de restrição de desigualdade. São apresentadas criticamente a teoria de lagrangeano aumentado, os modelos regularizados e o método estabilizado via mínimos quadrados. São feitas análises matemáticas para a nova formulação em termos de estabilidade, existência e unicidade de solução. Ordens de convergência ótimas são obtidas matematicamente, superando os métodos clássicos que também apresentam limitação para o valor de tensão limite. Resultados numéricos são apresentados confirmando a teoria aqui desenvolvida e mostrando a robustez do novo método para resolver problemas onde a tensão limite é muito elevada.

The discovery of the non-coding RNA (ncRNA) has been primarily focused on the genomes of eukaryotes and pathogenic bacteria. In vibrios, all that is known up to now regarding ncRNAs involves V. cholerae N16961 e V. campbellii ATCC BAA-1116. In this study, ncRNA candidate genes were identified in the genomes of V. campbellii ATCC BAA-1116, V. alginolyticus 40B, V. communis 1DA3 e V. mimicus VM573. V. alginolyticus 40B and V. campbellii ATCC BAA-1116 are abundant in brazilian corals, whereas V. mimicus VM573 is a toxic strain (carrying the Vibrio pathogenicity island) atypical to this species. In order to identify the ncRNAs in silico, the tools Infernal and Rfam database were used. Perl programs were developed in the present work. The Infernal tool and the Rfam database are based on the Covariance Model (CM), a special case of Stochastic Context Free Grammars (SCFG). Up to 38 ncRNAs were identified per species. They were classified into seven classes according to their regulatory function and/or structural (1. riboswitches, 2. modulators of protein activity, 3. RNA's antisensus of trans action, 4. RNA's antisensus of cis action, 5. ribonucleoproteins, 6. regulation by transcription termination and 7. unknown classification). The most abundant group was the riboswitch, whereas the less abundant group was the ribonucleoprotein. This work demonstrated that the ncRNAs show a great diversity in functional classes, possibly associated with the regulation of different cellular processes in vibrios, including regulation of pathogenicity. / A descoberta de RNA não-codificante (ncRNA) tem focado principalmente nos genomas de eucariontes e de bactérias patogênicas. Em vibrios, o que se conhece até o momento sobre ncRNAs envolve V. cholerae N16961 e V. campbellii ATCC BAA-1116. Neste estudo, são identificados genes candidatos de ncRNAs no genoma de V. campbellii ATCC BAA-1116, V. alginolyticus 40B, V. communis 1DA3 e V. mimicus VM573. V. alginolyticus 40B e V. campbellii ATCC BAA-1116 são abundantes em corais brasileiros, enquanto que V. mimicus VM573 é uma linhagem toxigênica (CT e TCP positiva) atípica desta espécie. Para identificar os ncRNAs através de análise in silico foram utilizadas ferramentas já disponíveis (Infernal e a base de dados Rfam) e programas em Perl desenvolvidos no presente trabalho. A ferramenta Infernal e a base de dados Rfam são baseados em modelo de covariância (CM), um caso especial de gramáticas estocásticas livres de contexto (SCFG). Foram identificados até 38 ncRNAs por espécie, os quais foram classificados em sete classes de acordo com sua função regulatória e /ou estrutural (riboswitches, moduladores da atividade de proteínas, RNAs antisenso de ação trans, RNAs antisenso de ação cis, ribonucleoproteinas, regulação por término de transcrição e classificação desconhecida). O grupo mais abundante foi o riboswitch, enquanto que o grupo menos abundante foi o ribonucleoproteina. Este trabalho demonstrou que os ncRNAs apresentam uma ampla diversidade de classes funcionais, estando possivelmente associados com a regulação de diferentes processos celulares em vibrio, incluindo a regulação da patogenicidade.

Caminhos aleatórios clássicos são essenciais para a Física, a Matemática, a Ciência da Computação e muitas outras áreas. Há uma grande expectativa que a sua versão quântica seja ainda mais poderosa, uma vez que o caminhante quântico se espalha quadraticamente mais rápido que o seu análogo clássico. Neste trabalho, estudamos o comportamento do caminhante quântico em uma e duas dimensões, além de generalizarmos o formalismo de ligações interrompidas para duas ou mais dimensões. Em uma dimensão, analisamos o comportamento do caminhante quântico, que além das duas possibilidades de deslocamento usuais, direita e esquerda, também permanece na posição atual. Em duas dimensões, apresentamos um estudo detalhado do comportamento do caminhante no plano e quando há descoerência gerada pela quebra aleatória das ligações para as posições vizinhas com uma certa probabilidade para cada uma das direções. Quando essa probabilidade de quebra é diferente nas duas direções encontramos um resultado não trivial que representa uma transição do caso 2-D descorente para o caso 1-D coerente. Também utilizamos o formalismo de ligações interrompidas para modelar o comportamento de um caminhante quântico que passa por uma e por duas fendas. Realizamos simulações com com as principais moedas e observamos conclusivamente os padrões de interferência e difração.

Neste trabalho desenvolvemos a modelagem computacional dos fenômenos inerentes ao acoplamento hidromecânico que governam o escoamento de dois fluidos imiscíveis em uma matriz porosa heterogênea e deformável. As equações do modelo na escala de Darcy são decompostas em dois subsistemas associados a poromecânica e ao transporte dos fluidos. Neste contexto novos métodos numéricos são propostos para a computação da velocidade de Darcy baseados em técnicas de pós-processamento de Petrov-Galerkin em conjunção com métodos localmente conservativos para a equação hiperbólica de transporte da saturação aliados à técnica de decomposição de operadores para a computação dos efeitos da evolução temporal da porosidade induzidos pela deformação da matriz porosa sobre o transporte. As simulações numéricas do modelo resultante nos permite identificar diferentes regimes do acoplamento hidromecânico durante o processo de extração secundária de petróleo. Em particular analisamos a influência da razão de viscosidade entre os fluidos e da heterogeneidade da matriz porosa sobre os diferentes regimes de acoplamento. Dentre os vários fenômenos capturados no modelo damos particular ênfase ao surgimento de um processo de compactação retardada do reservatório devido à inundação de água onde, em particular, ilustramos seu efeito sobre as curvas de produção de petróleo. No contexto da modelagem estocástica analisamos também os efeitos das heterogeneidades e incertezas presentes nos coeficientes de permeabilidade e das constantes elásticas do meio poroso sobre os diferentes regimes do acoplamento geomecânico. A caracterização destes regimes governados pela razão de viscosidade e pelo coeficiente de variação das heterogeneidades é ilustrada por meio de simulações numéricas do processo de extração secundária de um reservatório sujeito ao peso das camadas superiores. / In this work we develop the computational modeling of the hydromechanical couplings which govern two-phase flow in a heterogeneous poroelastic media. At the Darcy scale the governing equations are decomposed in two subsystems associated with the poromechanics and hydrodynamics. In this context new numerical methods are proposed for the computation of the Darcy velocity based on Petrov-Galerkin post processing techiniques in conjunction with locally conservative methods for the hyperbolic transport equation and for water saturation together with an operator splitting technique for the computation of the transient porosity effect upon the transport equation. Numerical simulations allow us to identify different regimes of hydromechanics coupling during the secondary of petroleum withdrawal.In particular, we analyze the influence of the viscosity ratio and strength of heterogeneity upon the various coupling regimes. Among the many phenomena captured by the model we give particular emphasis on the delayed compaction of the reservoir due to the water flooding illustrating its effects upon the oil production curves. Within the framework of the stochastic modelinf, we analyze the effects of the heterogeneity and the uncertainty in permeability and elastic coeddicientsupon the hydromechanical coupling regimes. The characterization of these regimes governed by yhe viscosity ratio and by the strength of heterogeneity is illustrated in numerical simulations of secondary oil withdrawal from a reservoir subject to the overburden due the weight of the overlaying formations.

Fenômenos em materiais heterogêneos conduzem ao estudo de problemas em equações diferenciais parciais com coeficientes altamente oscilatórios. O tratamento numérico mediante o uso dos métodos tradicionais exige um alto custo computacional ou é inviável. No presente trabalho pretendemos estender o método residual free bubbles com o intuito de gerar um procedimento de homegeneização numérica para o estudo de uma classe de problemas elípticos não lineares com coeficientes que têm um comportamento altamente variável (problemas multiescala).Mostramos que a formulação numérica decorrente da metodologia residual free bubbles permite aproximar o problema multiescala e, portanto, o problema efetivo. Para validar o procedimento proposto, apresentaremos estimativas de erro e resultados numéricos.

Optimization is a large area of knowledge concerned with the need of a better use of resources and activities, becoming indispensable in the solution of several problems which arise from the study and formulation of real-world problems. Furthermore, the constraints that must be respected for each situation introduce in the methodologies of optimization an additional complication. Differential Evolution, which in its original formulation is applied only to unconstrained optimization problems in continuous space, also provides good results when applied to constrained optimization with discrete and continuous variables. This work presents the necessary improvements to Differential Evolution for its proper application to this class of problems, and proposes a new combination of techniques for this application, as well as a mechanism for dynamic selection of the appropriate variant of the technique. The initial proposal is a combination of Differential Evolution with a technique of adaptive penalty (APM) and the second proposal concerns the dynamic selection of variants during the search process. Several computational experiments are carried out confirming the competitiveness of the proposed algorithms. / A otimização é uma grande área de conhecimento voltada para a necessidade de um melhor aproveitamento de recursos e atividades, tornando-se indispensável na resolução de grande parte dos problemas oriundos de estudos e formulações de problemas reais. Além disso, as restrições que devem ser respeitadas para cada situação introduzem nas metodologias de otimização um complicador adicional. A Evolução Diferencial, que em sua formulação original é aplicada somente a problemas de otimização irrestrita e em espaços contínuos, apresenta também bons resultados quando aplicada à otimização restrita com variáveis contínuas e discretas. Este trabalho apresenta os aperfeiçoamentos necessários à Evolução Diferencial para sua adequada aplicação sobre essa classe de problemas, além de propor uma nova combinação de técnicas para essa aplicação, bem como um mecanismo de seleção dinâmica da variante adequada da técnica. A proposta inicial é a combinação da Evolução Diferencial com uma técnica adaptativa de penalização (APM) e a segunda proposta visa a seleção dinâmica de variantes durante o processo de busca. Vários experimentos computacionais são executados confirmando a competitividade dos algoritmos propostos.