Esta dissertação de mestrado aborda formulações computacionais e algoritmos para a busca e extração de padrões em cadeias biológicas. Em particular, o presente texto concentra-se nos dois problemas a seguir, considerando-os sob as distâncias de Hamming e Levenshtein: a) como determinar os locais nos quais um dado padrão ocorre de modo aproximado em uma cadeia fornecida; b) como extrair padrões que ocorram de modo aproximado em um número significativo de cadeias de um conjunto fornecido. O primeiro problema, para o qual já existem diversos algoritmos polinomiais, tem recebido muita atenção desde a década de 60, e ganhou novos ares com o advento da biologia computacional, nos idos dos anos 80, e com a popularização da Internet e seus mecanismos de busca: ambos os fenômenos trouxeram novos obstáculos a serem superados, em razão do grande volume de dados e das bastante justas restrições de tempo inerentes a essas aplicações. O segundo problema, de surgimento um pouco mais recente, é intrinsicamente desafiador, em razão de sua complexidade computacional, do tamanho das entradas tratadas nas aplicações mais comuns e de sua dificuldade de aproximação. Também é de chamar a atenção o seu grande potencial de aplicação. Neste trabalho são apresentadas formulações adequadas dos problemas abordados, assim como algoritmos e estruturas de dados essenciais ao seu estudo. Em especial, estudamos a extremamente versátil árvore dos sufixos, assim como uma de suas generalizações e sua estrutura irmã: o vetor dos sufixos. Grande parte do texto é dedicada aos filtros baseados em q-gramas para a busca aproximada de padrões e algumas de suas mais recentes variações. Estão cobertos os algoritmos bit-paralelos de Myers e Baeza-Yates-Gonnet para a busca de padrões; os algoritmos de Sagot para a extração de padrões; os algoritmos de filtragem de Ukkonen, Jokinen-Ukkonen, Burkhardt-Kärkkäinen, entre outros. / This thesis deals with computational formulations and algorithms for the extraction and search of patterns from biological strings. In particular, the present text focuses on the following problems, both considered under Hamming and Levenshtein distances: 1. How to find the positions where a given pattern approximatelly occurs in a given string; 2. How to extract patterns which approximatelly occurs in a certain number of strings from a given set. The first problem, for which there are many polinomial time algorithms, has been receiving a lot of attention since the 60s and entered a new era of discoveries with the advent of computational biology, in the 80s, and the widespread of the Internet and its search engines: both events brought new challenges to be faced by virtue of the large volume of data usually held by such applications and its time constraints. The second problem, much younger, is very challenging due to its computational complexity, approximation hardness and the size of the input data usually held by the most common applications. This problem is also very interesting due to its potential of application. In this work we show computational formulations, algorithms and data structures for those problems. We cover the bit-parallel algorithms of Myers, Baeza-Yates-Gonnet and the Sagots algorithms for patterns extraction. We also cover here the oustanding versatile suffix tree, its generalised version, and a similar data structure: the suffix array. A significant part of the present work focuses on q-gram based filters designed to solve the approximate pattern search problem. More precisely, we cover the filter algorithms of Ukkonen, Jokinen-Ukkonen and Burkhardt-Kärkkäinen, among others.

This thesis deals with the problem of approximate string matching, also called string matching allowing errors. The thesis targets the area of offline algorithms, which allows very fast pattern matching thanks to index created during initial text preprocessing phase. Initially, we will define the problem itself and demonstrate variety of its applications, followed by short survey of different approaches to cope with this problem. Several existing algorithms based on suffix trees will be explained in detail and new hybrid algorithm will be proposed. Algorithms wil be implemented in C programming language and thoroughly compared in series of experiments with focus on newly presented algorithm.

This work deals with conception and implemetation of tools for finding approximate palindromes in DNA sequences. The work focuses on the description of DNA structure, and on the function of palindromes in DNA sequences, and on the description of methods for finding approximate palindromes. Main part of thesis is focused on conclusion and description of implementation approximate palidromes finding tool.

In this study an attempt is made to describe the morphological apects of Tshiguvhu. In chapter 1, it is indicated that historically, there was extensive early contact between Vhaguvhu and Balobedu and Tlokwa. In ,chapters 2 and 3, nouns and pronouns are analysed morphologically. Some similarities and differences between Tshiguvhu and Tshivenda are highlighted. These differences are ascribed to influences from Lobedu and Tlokwa. In chapters 4 and 5, the form of the verb and the use of verb forms in various tenses, where applicable, are described morphologically. Some verb roots and extensions have been influenced by Northern Sotho dialects whereas some have not. In chapter 6, the morphology of adverbs, interrogatives, conjunctions, ideophones and interjections are briefly described. In conclusion, it is indicated that Tshiguvhu is a dialect of Venda because of its cultural and historical bonds with Venda, although linguistically it shares some features with certain Northern Sotho dialects. / African Languages / M.A. (African Languages)

In the literature, Cognitive radio (CR) as well as full-duplex (FD) communication technologies are proposed to increase the spectrum efficiency. The main contribution of this thesis is to introduce prediction and estimation techniques with low control overhead, and use the predicted or estimated information in resource allocation in CR networks, both in the overlay networks and the underlay networks. Prediction and estimation are important in increasing the data rate and keeping the interference at a low level. In the overlay scheme, I modeled the primary user (PU) traffic characteristics of the channels using the Probabilistic Suffix Tree (PST) algorithm. Then using this PST algorithm, I introduced a frequency hopping based control channel and derived its theoretical properties. Then I proposed two methods for selecting a channel set for transmission, which took into account both the PU channel usage statistics and, secondary user (SU) channel usage statistics as perceived by an SU of interest. The first scheme selected channels having the highest probability of successful transmission, while the second calculated a net reward using a marked Markov chain. Then using simulations, I showed that our scheme caused acceptable interference to the PUs and has better throughput performance, compared to a scheme selecting channels randomly. Then I proposed two joint channel assignment and power allocation schemes for a bi-directional FD underlay CR network with network assistance. The first scheme used the information on the number of total SU pairs present in the network. In the second scheme, I used least squares based estimation and Kalman filtering to estimate the interference at the monitoring stations using the local interference. It reduced the control overhead of keeping track of active SUs. In both of these schemes each SU pair decided on the channels to be used in the half-duplex mode and the full-duplex mode using local information. This joint optimization was done running channel assignment and power allocation algorithms alternatively. In the power allocation problem, I used a technique called monotonic optimization. After simulating both of these schemes I showed that the scheme based on estimation performs satisfactorily given that it has less control overhead. / October 2016

In this thesis we investigate several methods how to improve the quality of statistical machine translation (MT) by using linguistically rich information. First, we describe SemPOS, a metric that uses shallow semantic representation of sentences to evaluate the translation quality. We show that even though this metric has high correlation with human assessment of translation quality it is not directly suitable for system parameter optimization. Second, we extend the log-linear model used in statistical MT by additional source-context model that helps to better distinguish among possible translation options and select the most promising translation for a given context.

Aim of this MA thesis is to describe Spanish diminutives from different points of view. After defining basic concepts from morphology and lingu- istics the study focuses on traditional and pragmatic semantics of Spanish diminutives. The pragmatic point of view is the basis for analysis of particu- lar diminutives. In the conclusion, the traditional and pragmatic approaches to Spanish diminutives are compared.

Ce travail étudie les déviations de sommes ergodiques pour des systèmes dynamiques substitutifs avec une matrice qui admet des valeurs propres de module supérieur à 1. Précisément, nous nous concentrons sur les substitutions telle que ces valeurs propres ne sont pas conjuguées. Dans un premier temps, on défini les lettres a-minimales et dominantes d'un mot pour étudier sa ligne brisée associé. On défini la ligne brisée normalisée et sa fonction limite. Pour l'étude des sommes ergodiques, on défini le sous-automate des lettres minimales. On donne des conditions sur une substitution de sorte qu'il y ait un nombre infini des sommes ergodiques égales à zéro pour un point x 2 X. Enfin, en utilisant un boucle dans une classe de Rauzy, on prouve l'existence d'un nombre infini d'échanges d'intervalles auto-similaires, dont la matrice de Rauzy a deux valeurs propres non conjuguées de module supérieur à 1. Et tout échange d'intervalles affine semi-conjugué à cet échange d'intervalles est aussi conjugué. / This thesis focuses on the deviation of ergodic sums for a substitution dynamical systems with a matrix that admits eigenvalues of modulus larger than 1. Specifically, we concentrate on substitutions with non-conjugated eigenvalues. At first, we define the a-minimals letters and the dominant letters of a word to study its broken associated line. We define the normalize broken line and its limit function. For the study of ergodic sums, we define the sub-automaton of minimum letters. We give conditions on a substitution so that there is infinitely many zero sums ergodic for a point x 2 X. Finally, using a loop in a class of Rauzy, we prove the existence of infinitely many interval exchange transformation self-similar, whose Rauzy matrix has two non-conjugated eigenvalues larger than 1 and every affine interval exchange transformation that is semi-conjugated, is also conjugated.

O presente trabalho, resultado das pesquisas do GMHP, Grupo de Mofologia Histórica do Português, procura estudar os aspectos sincrônicos e diacrônicos do sufixo -ístico(a), bem como as relações existentes com o seu desdobramento -ística e com os sufixos -ismo e -ista, no português e no galego, para justificar, então, sua mudança morfológica de atuação deverbal para denominal, bem como as suas demais mudanças semânticas e as línguas responsáveis pela sua disseminação. Para tanto, utilizando-se a metodologia desenvolvida pelo grupo, e com corpora lexicográfico, historiográfico, ademais de literário e jornalístico, procura-se inicialmente por meio da elaboração de uma prospecção geral, estabelecer o período de início de atuação do sufixo além de verificar como é entendido pelas obras lingüísticas atuais nas duas línguas em estudo. Em seguida, estuda-se a sua gênese greco-latina e, posteriormente, sua atuação em outras línguas, como também suas relações sintagmáticas e paradigmáticas com os demais sufixos envolvidos, para se estabelecer uma evolução ao longo dos séculos, por meio da elaboração de classificações semântico-funcionais de cada período estudado, bem como avaliar a importância das línguas de cultura e dos processos de tradução na disseminação dos sufixos em questão. Nesse sentido, com a construção do glossário de datações e abonações de palavras formadas com o sufixo -ística, desdobramento de -ístico(a), pode-se verificar a grande importância da língua alemã, em detrimento da francesa, na veiculação do sufixo. Finalmente, com a análise da produtividade de -ístico(a) no português, mostra-se que um sufixo não é apenas provido de significado semântico e funcional, mas também é constituído vários outros matizes, dentre eles os que caracterizam o gênero textual em que atua. / The present work, a result of researches carried out by the GHMP (GMHP in Portuguese) - Group of Historical Morphology of the Portuguese Language - aims at studying both the synchronic and diachronic aspects of the suffix -ístico(a), as well as its existing relations with its evolution -ística and with the suffixes -ismo and -ista in Portuguese and Galician, in order to justify its morphological change from a deverbal to a denominal nature, its further semantic changes as well as the languages responsible for its dissemination. For such, by making use of the method evolved by the group and with lexicographical, historiographical, not to mention literary and journalistic corpora, initially we aim by means of the elaboration of a general prospection, to establish the initial period of functioning of the suffix besides observing how it is understood by the present linguistic works in the two languages under study. Then, its Greco-Latin genesis and subsequently its functioning in other languages are analyzed as well as its syntagmatic and paradigmatic relations with the other suffixes involved in order to establish an evolution throughout the centuries by means of the elaboration of functional-semantic classifications of each period under study, as well as to assess the importance of languages of culture and of processes of translations in the dissemination of the suffixes in question. Thus, with the construction of a glossary of dating and sample sentences of formations with -ística, the evolution of -ístico(a), the great importance of the German language, unlike the French language, in the diffusion of the suffix can be observed. Finally, with the analysis of the productivity of -ístico(a) in Portuguese, it can be demonstrated that a suffix is not only possessed by both a semantic and functional meaning, but is also constituted by various other nuances, among which the ones that characterize the textual gender in which it functions.

Existem autores que consideram os sufixos como unidades mínimas vazias de significado que não alteram a classe gramatical da base a que se integram para formar novos vocábulos. Todavia, inúmeros exemplos refutam tais afirmações (de adjetivos podemos derivar substantivos abstratos: feliz felicidade; o sufixo eiro pode compor substantivos, como pedreiro, assim como adjetivos, interesseiro). Desta forma, percebemos que os sufixos possuem significado autônomo e que fazem mais do que alterar a classe gramatical de um termo. O objetivo desta pesquisa é tratar do sufixo dade na língua portuguesa, ressaltando, por meio de paráfrases semânticas, os sentidos diacronicamente atestados em gramáticas e dicionários de língua portuguesa, especialmente no Dicionário eletrônico Houaiss da língua portuguesa (2001). Acreditamos que este tipo de análise colabora com estudos de sentidos e de datações atribuídos ao sufixo. Esta pesquisa se enquadra nas propostas do Grupo de Morfologia Histórica do Português da Universidade de São Paulo (GMHP/USP, http://www.usp.br/gmhp), sob a coordenação do Prof. Dr. Mário Eduardo Viaro. / There are some authors who consider suffixes as minimum units with no meaning that cannot form a word with a different morphological category from its basis. However, a lot of examples could be easily taken to refute such ideas (from adjectives abstract nouns can be derived: feliz felicidade; the Portuguese suffix eiro can be a compound of nouns, such as pedreiro, or adjectives, interesseiro). This shows us how suffixes carry an autonomy in their meaning and not only change the grammatical category of a derived word. The aim of this research is to analyze the Portuguese suffix dade, showing, through semantic paraphrases, the meanings diachronically presented in grammar books and dictionaries on Portuguese, especially in the Dicionário eletrônico Houaiss da língua portuguesa (2001). We argue that this type of analysis could enrich the studies about meanings and date occurrences associated to this particular suffix. This work is inserted within the purposes of the Grupo de Morfologia Histórica do Português da Universidade de São Paulo (GMHP/USP, Group of Historical Morphology of the Portuguese Language, http://www.usp.br/gmhp), under PhD. Mário Eduardo Viaro coordination.