O presente trabalho, resultado das pesquisas do Grupo de Morfologia Histórica do Português, procura estudar os aspectos semânticos do sufixo -ista no português e no galego, baseando-se na afirmação de VIARO (2005), segundo a qual a semântica da base é diferente da semântica do sufixo e da semântica da palavra formada pela derivação com este, e ressaltando, que não necessariamente a semântica da palavra formada é a soma das semânticas do sufixo e base. Desde esta ótica, traça-se, inicialmente, um panorama histórico e um mapeamento geral da semântica das palavras derivadas com o sufixo proveniente da terminação grega -#953;στης em várias línguas, e, posteriormente, faz-se um estudo em corpora das línguas portuguesa e galega, propondo-se uma classificação semântica das palavras formadas com o sufixo -ista, a qual, detalhada por perspectivas históricas e etimológicas, conduz a uma classificação semântica do sufixo -ista, no português e no galego. / The present work, which is the result of the researches carried out by the Grupo de Morfologia Histórica do Português [\"Group of Historical Morphology of the Portuguese Language\"], studies the semantic aspects of the suffix -ista, in Portuguese and Galician, based on VIARO\'s (2005) assertion, according to which the base semantics is different from the suffix semantics and also different from the semantics of the word formed by the derivation with this suffix, and the semantics of the word formed isn\'t necessarily the sum of the base semantics with the suffix semantics. From this standpoint, we initially draw a historical overview and a general map of the semantics of the words derived with the suffix originating from the Greek ending -ιστης, in several languages. Based on an analysis of the Portuguese corpora and the Galician corpora, we subsequently propose a semantic classification of the words formed by the suffix -ista, which, after providing a detailed historical and etymological perspective, leads to a semantic classification of the suffix -ista, in the Portuguese and Galician languages.

Jag har i denna uppsats valt ut ett område i Dresdens absoluta centrum och undersökt gatunamn ur ett morfologiskt och etymologiskt perspektiv. När det gäller det morfologiska har jag analyserat de ingående suffixen och fogeelementen (-er,      -itz, -ner, -en- och -s-). Det etymologiska har utgått från olika namngivningsprinciper för gatunamnen: efter personer, utseende, yrken och färger. Namn efter läge och funktion har fått utgå, då de inte rymts inom ramen för denna undersökning. Det har gjort att jag kunnat granska totalt 60 av de 98 ingående gatorna i centrumområdet i Dresden. Jag har dels använt mig av Google kartor och dels några viktigare böcker (Das Namenbuch der Straßen und Plätze im 26er Ring Dresden, Wortbildung der deutschen Gegenwartssprache och Wortbildung des modernen Deutschen - Ein Lehr- und Übungsbuch). Mina resultat i denna uppsats är att de gator som heter något med gränder är de äldsta, att August den Starkes familj fick ett stort antal gator uppkallade efter sig, och att det blev mode att uppkalla gator efter manliga borgerliga personer, att kvinnor fick gator uppkallade efter sig först i början av 1900-talet. Vidare resultat är att namn med fogeelement blev ovanliga under andra delen av 1700-talet, att det finns få slaviska influenser på gatunamnen i Dresden, att alla nazistiska namn ändrades efter andra världskriget, att alla kommunistiska namn ändrades i Dresden efter 1989, men inte nödvändigtvis i andra delar av Tyskland, till exempel Berlin och Leipzig.

Ingeniero Civil en Computación / El árbol de sufijos es una de las estructuras más importantes que se han creado para el manejo de cadenas de caracteres. Esta estructura permite encontrar eficientemente las ocurrencias de un patrón, en tiempo proporcional al largo del patrón. Adicionalmente soporta operaciones para resolver problemas complejos sobre una secuencia. Esta estructura tiene muchas aplicaciones en variadas áreas de la investigación , destacándose en la bioinformática, donde los recientes avances tecnológicos han permitido recolectar grandes colecciones de secuencias de ADN. La implementación clásica se vuelve impracticable para grandes volúmenes de información dado que ocupan demasiado espacio, que siempre muchas veces mayor que el texto mismo. Luego, no pueden ser almacenados en memoria principal, lo que en la práctica significa un aumento importante del tiempo de respuesta. Este problema es la principal motivación por la cual se buscan nuevas representaciones comprimidas de esta estructura, dando lugar a los árboles de sufijos comprimidos. Estos contienen la misma información que los árboles de sufijos pero ocupan un espacio considerablemente menor. Existen variadas propuestas teóricas para representar un árbol de sufijos comprimido, que ofrecen espacios y tiempos diferentes. En la práctica, dos estructuras destacan por sobre las demás. La primera fue propuesta por Sadakane e implementada por Välimäki et al. Esta estructura soporta la mayoría de las operaciones de navegación en tiempo constante, pero en la práctica requiere entre 25 y 35 bits por símbolo. La segunda fue propuesta por Fischer et al. e implementada por Cánovas, incorporando variantes y nuevas ideas para todas las estructuras que componen el árbol de sufijos comprimido propuesto por ellos. Una de estas variantes resulta ser superior a la implementación de Sadakane tanto en espacio como en tiempo, utilizando alrededor de 8 a 12 bits por símbolo. Dado que secuencias de ADN relacionadas son altamente similares, por ejemplo dos genomas humanos son muy parecidos, las colecciones pueden ser tratadas como un gran texto que contiene cadenas altamente similares. En este trabajo se propone e implementa una nueva variante del árbol de sufijos comprimido de Fischer et al, optimizada para textos altamente repetitivos. Se reemplazan y/o modifican cada una de las estructuras que componen el árbol por nuevas que presentan mayor compresión en textos repetitivos. El resultado más importante consiste en crear una nueva estructura inspirada en una técnica de compresión basada en gramáticas, aplicable al árbol de sufijos comprimido, que con poco espacio extra acelera considerablemente las operaciones sobre el árbol. Finalmente, la variante se compara experimentalmente sobre textos altamente repetitivos y resulta ser superior a la implementación de Cánovas, tanto en tiempo como en espacio, ocupando entre 3 a 6 bits por símbolo. / Este trabajo ha sido parcialmente financiado por el Instituto Milenio de Dinámica Celular y Biotecnología (ICDB) y el proyecto Fondecyt 1-080019

No description available.

Presented thesis deals with the word-formation processes involved in creating new verbs in presen-day Italian. These processes are mainly derivational, namely prefixation, suffixation, conversion, including parasynthesis and back-formation, these two create mostly verbs. Compound verbs are rare in Italian and the number of verbal loanwords is low as well. The first part of the thesis describes these processes from theoretical point of view. The second part presents the descriptive analysis of 330 verbs created between 1976-2001. These verbs were extracted from the eletronic version of Dizionario Italiano Sabatini-Coletti and they were categorized by the process involved in their creation. The productivity of each process and then affixes was also studied.

La bioinformática es la aplicación de las ciencias computacionales a la gestión y análisis de datos biológicos. A partir de 2005, con la aparición de los secuenciadores de ADN de nueva generación surge lo que se conoce como Next Generation Sequencing o NGS. Un único experimento biológico puesto en marcha en una máquina de secuenciación NGS puede producir fácilmente cientos de gigabytes o incluso terabytes de datos. Dependiendo de la técnica elegida este proceso puede realizarse en unas pocas horas o días. La disponibilidad de recursos locales asequibles, tales como los procesadores multinúcleo o las nuevas tarjetas gráfi cas preparadas para el cálculo de propósito general GPGPU (General Purpose Graphic Processing Unit ), constituye una gran oportunidad para hacer frente a estos problemas. En la actualidad, un tema abordado con frecuencia es el alineamiento de secuencias de ADN. En bioinformática, el alineamiento permite comparar dos o más secuencias de ADN, ARN, o estructuras primarias proteicas, resaltando sus zonas de similitud. Dichas similitudes podrían indicar relaciones funcionales o evolutivas entre los genes o proteínas consultados. Además, la existencia de similitudes entre las secuencias de un individuo paciente y de otro individuo con una enfermedad genética detectada podría utilizarse de manera efectiva en el campo de la medicina diagnóstica. El problema en torno al que gira el desarrollo de la tesis doctoral consiste en la localización de fragmentos de secuencia cortos dentro del ADN. Esto se conoce bajo el sobrenombre de mapeo de secuencia o sequence mapping. Dicho mapeo debe permitir errores, pudiendo mapear secuencias incluso existiendo variabilidad genética o errores de lectura en el mapeo. Existen diversas técnicas para abordar el mapeo, pero desde la aparición de la NGS destaca la búsqueda por pre jos indexados y agrupados mediante la transformada de Burrows-Wheeler [28] (o BWT en lo sucesivo). Dicha transformada se empleó originalmente en técnicas de compresión de datos, como es el caso del algoritmo bzip2. Su utilización como herramienta para la indización y búsqueda posterior de información es más reciente [22]. La ventaja es que su complejidad computacional depende únicamente de la longitud de la secuencia a mapear. Por otra parte, una gran cantidad de técnicas de alineamiento se basan en algoritmos de programación dinámica, ya sea Smith-Watterman o modelos ocultos de Markov. Estos proporcionan mayor sensibilidad, permitiendo mayor cantidad de errores, pero su coste computacional es mayor y depende del tamaño de la secuencia multiplicado por el de la cadena de referencia. Muchas herramientas combinan una primera fase de búsqueda con la BWT de regiones candidatas al alineamiento y una segunda fase de alineamiento local en la que se mapean cadenas con Smith-Watterman o HMM. Cuando estamos mapeando permitiendo pocos errores, una segunda fase con un algoritmo de programación dinámica resulta demasiado costosa, por lo que una búsqueda inexacta basada en BWT puede resultar más e ficiente. La principal motivación de la tesis doctoral es la implementación de un algoritmo de búsqueda inexacta basado únicamente en la BWT, adaptándolo a las arquitecturas paralelas modernas, tanto en CPU como en GPGPU. El algoritmo constituirá un método nuevo de rami cación y poda adaptado a la información genómica. Durante el periodo de estancia se estudiarán los Modelos ocultos de Markov y se realizará una implementación sobre modelos de computación funcional GTA (Aggregate o Test o Generate), así como la paralelización en memoria compartida y distribuida de dicha plataforma de programación funcional. / Salavert Torres, J. (2014). Inexact Mapping of Short Biological Sequences in High Performance Computational Environments [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/43721 / TESIS

This thesis presents a look at the suitability of Suffix Trees for full text indexing and retrieval. Typically suffix trees are built on a character level, where the tree records which characters follow each other character. By building suffix trees for documents based on words instead of characters, the resulting tree effectively indexes every word or sequence of words that occur in any of the documents. Ukkonnen's algorithm is adapted to build word-level suffix trees. But the primary focus is on developing Algorithms for searching the suffix tree for exact and approximate, or fuzzy, matches to arbitrary query strings. A proof-of-concept implementation is built and compared to a Lucene index for retrieval over a subset of the Reuters RCV1 data set.

No description available.

There are at least two reasons to have an efficient algorithm for identifying all maximal Lyndon substrings in a string: first, in 2015, Bannai et al. introduced a linear algorithm to compute all runs in a string that relies on knowing all maximal Lyndon substrings of the input string, and second, in 2017, Franek et al. showed a linear co-equivalence of sorting suffixes and sorting maximal Lyndon substrings of a string (inspired by a novel suffix sorting algorithm of Baier). In 2016, Franek et al. presented a brief overview of algorithms for com- puting the Lyndon array that encodes the knowledge of maximal Lyndon substrings of the input string. It discussed four different algorithms. Two known algorithms for computing the Lyndon array: a quadratic in-place algorithm based on iterated Duval’s algorithm for Lyndon factorization and a linear algorithmic scheme based on linear suffix sorting, computing the inverse suffix array, and applying the NSV (Next Smaller Value) algorithm. The overview also discusses a recursive version of Duval’s algorithm with a quadratic complexity and an algorithm emulating the NSV approach with a possible O(n log(n)) complexity. The authors at that time did not know of Baier’s algorithm. In 2017, Paracha proposed in her Ph.D. thesis an algorithm for the Lyndon array. The proposed algorithm was interesting as it emulated Farach’s recursive approach for computing suffix trees in linear time and introduced τ-reduction; which might be of independent interest. This was the starting point of this Ph.D. thesis. The primary aim is: (a) developing, analyzing, proving correct, and implementing in C++ a linear algorithm for computing the Lyndon array based on Baier’s suffix sorting; (b) analyzing, proving correct, and implementing in C++ the algorithm proposed by Paracha; and (c) empirically comparing the performance of these two algorithms with the iterative version of Duval’s algorithm. / Dissertation / Doctor of Philosophy (PhD)

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.