A comparação de sequências finitas é uma ferramenta que é utilizada para a solução de problemas em várias áreas. Comparamos sequências inferindo quais são as operações de edição de substituição, inserção e remoção de símbolos que transformam uma sequência em uma outra. As matrizes de pontuação são estruturas largamente utilizadas e que definem um custo para cada tipo de operação de edição. Uma matriz de pontuação G é indexada pelos símbolos do alfabeto. A entrada de G na linha A, coluna B mede o custo da operação de edição para substituir o símbolo A pelo símbolo B. As matrizes de pontuação induzem funções que atribuem uma pontuação para um conjunto de operações de edição. Algumas dessas funções para a comparação de duas e de várias sequências são estudadas nesta tese. Quando cada símbolo de cada sequência é editado exatamente uma vez para transformar uma sequência em outra, o conjunto de operações de edição pode ser representado por uma estrutura conhecida por alinhamento. Descrevemos uma estrutura para representar o conjunto de operações de edição que não pode ser representado por um alinhamento convencional e descrevemos um algoritmo para encontrar a pontuação de uma sequência ótima de operações de edição usando um algoritmo conhecido para encontrar a pontuação de um alinhamento convencional ótimo. Considerando três diferentes funções induzidas de pontuação, caracterizamos, para cada uma delas, a classe das matrizes para as quais as funções induzidas de pontuação são métricas nas sequências. Dadas duas matrizes de pontuação G e G\', dizemos que elas são equivalentes para uma dada função que é induzida por uma matriz de pontuação e que avalia a qualidade de um alinhamento se, para quaisquer dois alinhamentos A e B, vale o seguinte: o alinhamento A é ``melhor\'\' do que o alinhamento B considerando a matriz G se e somente se A é ``melhor\'\' do que o alinhamento B considerando a matriz G\'. Neste trabalho, determinamos condições necessárias e suficientes para que duas matrizes de pontuação sejam equivalentes. Finalmente, definimos três novos critérios para pontuar alinhamentos de várias sequências. Todos os critérios consideram o comprimento do alinhamento além das operações de edição por ele representadas. Para cada um dos critérios definidos,propomos um algoritmo e o problema de decisão correspondente mostramos ser NP-completo. / Comparison of finite sequences is a tool used to solve problems in several areas. In order to compare sequences, we infer which are the edit operations of substitution, insertion and deletion of symbols that transform one sequence into another. Scoring matrices are a widely used structure to define a cost for each type of edit operation. A scoring matrix G is indexed by symbols of an alphabet. The entry in G in row A and column B measures the cost of the edit operation for replacing symbol A by symbol B. Scoring matrices induce functions that assign a score for a set of edit operations. Some of these functions for comparing two and multiple sequences are studied in this thesis. If each symbol is edited exactly once for transforming a sequence into another, the set of edit operations can be represented by a structure called alignment. We describe a structure to represent the set of edit operations that cannot be represented by a conventional alignment and we design an algorithm to find the cost of an optimal sequence of edit operations by using a known algorithm to find the cost of an optimal alignment. Considering three different kinds of induced scoring functions, we characterize, for each one of them, the class of matrices for which the induced scoring functions are metrics on sequences. Given two scoring matrices G and G\', we say they are equivalent for a given function that is induced by a scoring matrix and that evaluates the quality of an alignment if, for any two alignments A and B of two sequences, we have the following: alignment A is ``better\'\' than B considering scoring matrix G if and only if A is ``better\'\' than B considering scoring matrix G\'. In this work, we determine necessary and sufficient conditions for scoring matrices to be equivalent. Finally, we define three new criteria for scoring alignments of several sequence. Every criterion considers the length of the alignment and the edit operations represented by it. An algorithm for each criterion is studied and the corresponding decision problem is shown to be NP-complete.

A comparação de sequências finitas é uma ferramenta que é utilizada para a solução de problemas em várias áreas. Comparamos sequências inferindo quais são as operações de edição de substituição, inserção e remoção de símbolos que transformam uma sequência em uma outra. As matrizes de pontuação são estruturas largamente utilizadas e que definem um custo para cada tipo de operação de edição. Uma matriz de pontuação G é indexada pelos símbolos do alfabeto. A entrada de G na linha A, coluna B mede o custo da operação de edição para substituir o símbolo A pelo símbolo B. As matrizes de pontuação induzem funções que atribuem uma pontuação para um conjunto de operações de edição. Algumas dessas funções para a comparação de duas e de várias sequências são estudadas nesta tese. Quando cada símbolo de cada sequência é editado exatamente uma vez para transformar uma sequência em outra, o conjunto de operações de edição pode ser representado por uma estrutura conhecida por alinhamento. Descrevemos uma estrutura para representar o conjunto de operações de edição que não pode ser representado por um alinhamento convencional e descrevemos um algoritmo para encontrar a pontuação de uma sequência ótima de operações de edição usando um algoritmo conhecido para encontrar a pontuação de um alinhamento convencional ótimo. Considerando três diferentes funções induzidas de pontuação, caracterizamos, para cada uma delas, a classe das matrizes para as quais as funções induzidas de pontuação são métricas nas sequências. Dadas duas matrizes de pontuação G e G\', dizemos que elas são equivalentes para uma dada função que é induzida por uma matriz de pontuação e que avalia a qualidade de um alinhamento se, para quaisquer dois alinhamentos A e B, vale o seguinte: o alinhamento A é ``melhor\'\' do que o alinhamento B considerando a matriz G se e somente se A é ``melhor\'\' do que o alinhamento B considerando a matriz G\'. Neste trabalho, determinamos condições necessárias e suficientes para que duas matrizes de pontuação sejam equivalentes. Finalmente, definimos três novos critérios para pontuar alinhamentos de várias sequências. Todos os critérios consideram o comprimento do alinhamento além das operações de edição por ele representadas. Para cada um dos critérios definidos,propomos um algoritmo e o problema de decisão correspondente mostramos ser NP-completo. / Comparison of finite sequences is a tool used to solve problems in several areas. In order to compare sequences, we infer which are the edit operations of substitution, insertion and deletion of symbols that transform one sequence into another. Scoring matrices are a widely used structure to define a cost for each type of edit operation. A scoring matrix G is indexed by symbols of an alphabet. The entry in G in row A and column B measures the cost of the edit operation for replacing symbol A by symbol B. Scoring matrices induce functions that assign a score for a set of edit operations. Some of these functions for comparing two and multiple sequences are studied in this thesis. If each symbol is edited exactly once for transforming a sequence into another, the set of edit operations can be represented by a structure called alignment. We describe a structure to represent the set of edit operations that cannot be represented by a conventional alignment and we design an algorithm to find the cost of an optimal sequence of edit operations by using a known algorithm to find the cost of an optimal alignment. Considering three different kinds of induced scoring functions, we characterize, for each one of them, the class of matrices for which the induced scoring functions are metrics on sequences. Given two scoring matrices G and G\', we say they are equivalent for a given function that is induced by a scoring matrix and that evaluates the quality of an alignment if, for any two alignments A and B of two sequences, we have the following: alignment A is ``better\'\' than B considering scoring matrix G if and only if A is ``better\'\' than B considering scoring matrix G\'. In this work, we determine necessary and sufficient conditions for scoring matrices to be equivalent. Finally, we define three new criteria for scoring alignments of several sequence. Every criterion considers the length of the alignment and the edit operations represented by it. An algorithm for each criterion is studied and the corresponding decision problem is shown to be NP-complete.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-29T14:23:19Z No. of bitstreams: 1 dararaqueldefreitasfolly.pdf: 1531064 bytes, checksum: 8724dcb5591cdc3ee7ecbd7a408179d4 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-03-03T14:17:12Z (GMT) No. of bitstreams: 1 dararaqueldefreitasfolly.pdf: 1531064 bytes, checksum: 8724dcb5591cdc3ee7ecbd7a408179d4 (MD5) / Made available in DSpace on 2016-03-03T14:17:12Z (GMT). No. of bitstreams: 1 dararaqueldefreitasfolly.pdf: 1531064 bytes, checksum: 8724dcb5591cdc3ee7ecbd7a408179d4 (MD5) Previous issue date: 2013-03-07 / Este trabalho é um estudo de caso que se alinha com as pesquisas da Sociolinguística Interacional e analisa a interação professor-aluno como reveladora dos movimentos de aproximação e afastamento no contexto institucionalizado da escola. Postulando que haja uma ligação direta entre a interação professor-aluno e a aprendizagem, fez-se uma microanálise de duas aulas filmadas num projeto de arte procurando responder às seguintes questões: como se caracteriza a interação professor-aluno em uma aula de arte no Projeto Café com Pão Arte conFusão, em termos dos alinhamentos dos participantes e dos enquadres evocados nessa situação, e que elementos linguístico-discursivos e contextuais são relevantes nessa interação? Foram analisados os papeis sociais, as relações de poder e as ações comunicativas do professor que encontram resposta favorável no aluno e aquelas que criam barreiras à interação. Concluiu-se que, no contexto específico das aulas gravadas, a relação entre a interação professor-aluno e a aprendizagem pode existir, mas não é a principal responsável pelos resultados alcançados no Projeto. A professora, em seu papel específico, não se revelou diferente dos padrões típicos como se esperava; mas sua atuação como dramaturga constroi eficazmente a interação com os alunos e torna sugestiva a conjugação entre o ensino de língua e a arte. / This work is a case study which relates to Interactional Sociolinguistics researches and analyzes the teacher-student interaction as revealing the movement towards and away from the institutionalized context of the school. Postulating that there is a direct link between teacher-student interaction and learning, a micro-analysis of two lectures recorded on a art project was made in order to answer the following questions: how to characterize the teacher-student interaction in an art class at projeto Café com Pão Arte conFusão, in terms of alignments of participants and framings evoked on this situation, and which linguistic-discursive and contextual elements are relevant in this interaction? We analyzed the social roles, power relations and communicative actions of the teacher are favorable response on the student and those that create barriers to interaction. It was concluded that, in the specific context of recorded classes , the relationship between teacher-student interaction and learning can exist, but it is not the main responsible for the results achieved in this project. The teacher, on herspecific role did not revealed different from the typical patterns as it was expected, but her acting as a playwright makes effectively the interaction with the students and renders suggestive the conjugation between the teaching of language and art.

In recent decades, scientific data has become available in increasing sizes and precision. Therefore techniques to analyze and summarize the ever increasing datasets are of vital importance. A common form of scientific data, resulting from simulations as well as observational sciences, is in the form of scalar-valued function on domains of interest. The Morse-Smale complex is a topological data-structure used to analyze and summarize the gradient behavior of such scalar functions. This thesis deals with efficient parallel algorithms to compute the Morse-Smale complex as well as its application to datasets arising from cosmological sciences as well as structural biology. The first part of the thesis discusses the contributions towards efficient computation of the Morse-Smale complex of scalar functions de ned on two and three dimensional datasets. In two dimensions, parallel computation is made possible via a paralleizable discrete gradient computation algorithm. This algorithm is extended to work e ciently in three dimensions also. We also describe e cient algorithms that synergistically leverage modern GPUs and multi-core CPUs to traverse the gradient field needed for determining the structure and geometry of the Morse-Smale complex. We conclude this part with theoretical contributions pertaining to Morse-Smale complex simplification. The second part of the thesis explores two applications of the Morse-Smale complex. The first is an application of the 3-dimensional hierarchical Morse-Smale complex to interactively explore the filamentary structure of the cosmic web. The second is an application of the Morse-Smale complex for analysis of shapes of molecular surfaces. Here, we employ the Morse-Smale complex to determine alignments between the surfaces of molecules having similar surface architecture.

Ces travaux de thèse concernent la conception et l'étude d'algorithmes, d'une part pourprédire les quantités thermodynamiques et la structure secondaire des ARN, d'autre part pour l'alignement de séquences.Dans une première partie, nous appliquons un algorithme de Monte-Carlo pour approximer la densité d'états d'énergie des structures secondaires d'une séquence d'ARN, ou d'une hybridation de deux molécules d'ARN données. Nous montrons d'abord que la densité estimée par notre programme est aussi bonne que la densité exacte, et le temps d'exécution de notre programme est beaucoup plus rapide. Nous calculons ensuite la température de dénaturation d'une hybridation de deux molécules d'ARN. Nous montrons que nos températures de dénaturation sont plus proches des valeurs expérimentales que celles des deux autres programmes existants.Puis, dans une deuxième partie, nous implémentons un algorithme de programmation dynamique qui engendre des structures sous-optimales, dédié principalement à la prédiction des deux structures fonctionnelles des riboswitchs. Nous appliquons d'abord notre programme sur un riboswitch TPP dans lequel nous avons réussi à détecter les deux structures fonctionnelles. Nous montrons ensuite que les structures prédites par notre programme sont plus proches de la structure réelle par rapport aux cinq autres programmes existants, sur un échantillon de riboswitch purine.Enfin, dans une troisième partie, nous présentons un algorithme de recherche des alignements sous-optimaux de séquences pour améliorer la qualité d'alignement des séquences. Nous comparons d'abord nos alignement à ceux produits par l'algorithme de Needdleman-Wunsch. Nous prédissons plus d'alignements de référrence par rapport l'algorithme de Needdleman-Wunsch. Nous calculons ensuite les fréquences des paires de bases alignées et les entropies de position spécifique dans nos alignements sous-optimaux. Nous montrons que les entropies calculées à partir de notre programme sont plus corrélées que celles des autres programmes avec les positions des paires de résidus fiablement alignées selon BAliBASE. / This thesis concerns the design and study of algorithms, on the one hand to predict the thermodynamic quantities and the secondary structure of RNA, the other for sequence alignment.In the first part, we apply a Monte Carlo algorithm to approximate the density of states for secondary structures of a given RNA sequence, and for hybridizations of two RNA sequences. We first show that the density estimated by our program is as good as the exact density, and the execution time of our program is much faster. We then calculate the melting temperature for a hybridization of two RNA sequences. We show that our melting temperatures are closer to experimental values than the other two programs.Then in the second part, we implement a dynamic programming algorithm that generates sub-optimal structures, mainly dedicated to the prediction of functional structures of riboswitchs. We first apply our program on a TPP riboswitch in which we were able to detect both functional structures. We then show that the structures predicted by our program are closer to the real structure compared to five other existing programs, on a sample of purine riboswitch.Finally, in the third part, we present a novel algorithm to produce sub-optimal pairwise alignments. We first compare our alignments to those produced by the algorithm of Needdleman-Wunsch. We predict more reference alignments than the algorithm of Needdleman-Wunsch. We then calculate the frequencies and position-specific entropies from our sub-optimal alignments. We show that entropies calculated from our program are more correlated than other programs with locations in the core block of BAliBASE reference alignments.

<p>This study examines the distribution of adverbs among child heritage speakers of Spanish. As demonstrated by previous research, the grammar of Spanish heritage speakers can be compared to that of monolingual speakers, but with slight differences in their use and interpretation that can occur given their language dominance, usage, and exposition to the heritage language (Camacho & Kirova, 2018). In adverb placement, a relevant difference comes with verb-raising, a syntactic feature that allows the verb (V) to move in the sentence, and that is common in romance languages, but uncommon in morphologically poor languages such as English (Camacho & Sanchez, 2017; Guijarro-Fuentes & Larrañaga, 2011). Other differences in adverb distribution also stem directly from their semantic use and interpretation (Zagona, 2002), differences that may create instances of cross-linguistic influence or transfer between English and Spanish grammars. Hence, this study intends to study the extent to which these phenomena are produced in adverb placement, considering the patterns of language dominance, use, and exposure of the participants and current bilingual research discussing language transfer in bilingual grammars. Hence, an elicited production task was administered to 14 child heritage speakers of Spanish from the U.S. Midwest and to a comparison group, 25 child monolingual Spanish speakers from Mexico. Results suggest that child heritage speakers behave differently in their production of adverb placement compared to monolingual speakers, showing lower accuracy and little use of verb-raising structures that allow them to produce the post-verbal adverb position Sub-Verb-Adv-Obj. These findings suggest a different developmental path in the acquisition of adverb placement for heritage children in comparison to that of monolingual children.</p>