Thesis (M.Sc.(Hons.)) -- University of Western Sydney, 2007. / A thesis submitted in fulfilment of the requirements for the degree of Master of Science (Hons) to the University of Western Sydney, College of Health and Science, Centre for Plant and Food Science. Includes bibliography.

Orientador: Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T18:42:28Z (GMT). No. of bitstreams: 1 Rezende_GermanoAbudde_D.pdf: 1418033 bytes, checksum: 61d29b02274278ede5ffca797e26371a (MD5) Previous issue date: 2014 / Resumo: A geometria de distâncias é o estudo da geometria baseado no conceito de distância. Ela é útil em várias aplicações, onde os dados de entrada consistem de um conjunto incompleto de distâncias, e a saída é um conjunto de pontos no espaço euclidiano, que realiza as distâncias dadas. No Problema de Geometria de Distâncias (DGP), é dado um inteiro K > 0 e um grafo simples, não direcionado, G = (V,E,d), cujas arestas são ponderadas por uma função não negativa d. Queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Um DGPk (com K fixado) está fortemente relacionado a um outro tipo de problema, que trata dos possíveis completamentos de uma certa matriz de distâncias euclidianas. Este último pode ser visto, em um certo sentido, como o "dual do primeiro problema". Neste trabalho, exploramos essa dualidade com a finalidade de propor melhorias no método Branch-and-Prune aplicado a uma versão discreta do DGPk / Abstract: Distance Geometry is the study of geometry based on the concept of distance. It is useful in many applications where the input data consists of an incomplete set of distances, and the output is a set of points in some Euclidean space which realizes the given distances. In the Distance Geometry Problem (DGP), it is given an integer K > 0 and a simple undirected weighted graph G = (V,E,d), whose edges are weighted by a non-negative function d. We want to determine if there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space satisfying all distance constraints given by d. A DGPk (with K fixed) is closely related to another type of problem, which treats the possible completions of a certain Euclidean distance matrix. In some sense, this is the "dual" of the first problem. We explore this duality in order to improve the Branch-and-Prune method applied to a discrete version of the DGPk / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T22:04:46Z (GMT). No. of bitstreams: 1 Fidalgo_FelipeDelfiniCaetano_D.pdf: 5383479 bytes, checksum: 8f7bf5142b44fa99ea2742f6183ee1c6 (MD5) Previous issue date: 2015 / Resumo: Motivado por estudos em estruturas 3D de proteínas, biomoléculas imprescindíveis no estudo da vida, surgiu um problema chamado Discretizable Molecular Distance Geometry Problem (DMDGP) que provou ser NP-Difícil. Para resolvê-lo, existe um algoritmo da literatura, Branch & Prune (BP), que utiliza uma estratégia combinatória de exploração de uma árvore binária de soluções associada ao problema. Além disso, foram descobertas relações de simetria que permitem obter uma solução, a partir de outra, através de reflexões nos chamados vértices de simetria. Alguns pesquisadores passaram a realizar este trabalho em paralelo (ParallelBP), dividindo uma instância em sub-instâncias, resolvendo localmente com o BP (o que pode ser feito em duas direções) e unindo as sub-soluções com movimentos rígidos, com o intuito de determinar as soluções em menor tempo. Nossa proposta é fornecer uma estratégia Dividir-e-Conquistar para resolver o DMDGP, de modo a melhorar a abordagem em paralelo. Ela possui três estágios. Inicialmente, dividimos uma instância em sub-instâncias duas-a-duas sobrepostas através dos vértices de simetria. Depois, utiliza-se os chamados gaps para decidir a direção em que o BP deve fornecer a solução local. Por fim, utilizamos rotações baseadas na Álgebra de Quatérnios para combinar as sub-soluções em soluções factíveis / Abstract: Motived by studies in 3D structures of proteins, essential biomolecules for Life, arised a problem called Discretizable Molecular Distance Geometry Problem (DMDGP) which proved to be NP-Hard. Aiming to solve it, there is an algorithm in the literature, Branch & Prune (BP), which uses a combinatorial strategy of exploring a binary tree of solutions that is associated to the problem. Moreover, some symmetry relations have been discovered which allows the obtainance of one solution from the other one by means of reflections in the so-called symmetry vertices. Some researchers started to do this work using parallel computing (ParallelBP), dividing one instance into sub-instances, solving the problem locally with the BP (what can be done in two directions) and joining the sub-solutions with rigid movements, with the objective of determining the solutions in a smaller time. Our purpose, thus, is to provide a Divide-and-Conquer strategy to solve the DMDGP in order to improve the parallel version. It has three stages. Initially, the instance is divided into sub-instances two-by-two overlapping by means of the symmetry vertices. After, the so-called gaps are used to decide the direction that the BP ought to provide the local solution. Finally, we propose to use Quaternion Rotations to combine sub-solutions into feasible solutions / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

En bioinformatique structurale, une partie des méthodes computationnelles qui calculent les structures de protéines à l'aide de données expérimentales, effectuent une optimisation de la position des atomes sous les contraintes expérimentales mesurées sur le système étudié, ainsi que sous des contraintes provenant de la connaissance générique de la stéréochimie organique. Ces méthodes d'optimisation présentent l'inconvénient de ne pas garantir la détermination de la meilleure solution. De plus, la validation de l'optimisation se fait en comparant les résultats obtenus pour des calculs répétés, et le résultat d'un calcul est accepté dans la mesure où le même résultat est obtenu plusieurs fois. Par cette approche, on rend plus difficile la détection de conformations alternatives de protéines, qui sont pourtant le sujet d'un vif intérêt dans la littérature. En effet, le développement de la sensibilité des techniques de résonance magnétique nucléaire (RMN) a permis de mettre en évidence plusieurs cas d'échange conformationnel reliés à la fonction des protéines. Dans ce projet de thèse, nous avons étudié une nouvelle approche pour le calcul de structures des protéines et l'exploration de leurs espaces conformationnels, basée sur la résolution du problème de Géométrie de Distance associé aux contraintes de distances dans une protéine par l'algorithme "interval Branch and Prune". Le logiciel implémentant cette méthode est appelée iBPprot, il incarne l'une des premières tentatives d'échantillonnage exhaustive des espaces conformationnels des protéines. Dans un premier temps, on s'est intéressé à l'application de la méthode en utilisant exclusivement des constraintes de distances exactes. Les résultats ont démontré que iBPprot était capable de reconstruire des structures références en s'appuyant seulement sur quelques contraintes à courte portée. De plus, la reconstruction a été d'une précision telle que la conformation générée présentait un RMSD de 1 Angstrom maximum avec la structure référence. L'exploration exhaustive de l'espace conformationnel a été possible pour une bonne partie des protéines cibles. Les temps de calcul pour l'exploration des espaces conformationnels ont été très variables allant de quelques secondes pour quelques protéines jusqu'à des semaines pour d'autres. L'évaluation de la qualité des structures obtenues a démontré qu'au moins 68% des valeurs de phi et psi sont localisées dans la zone 'core' du diagramme de Ramachandran. Cependant, des clash stériques ont été détectées dans plusieurs conformations mettant en jeu jusqu'à 7% d'atomes dans quelques unes de ces conformations. Dans un deuxième temps, on s'est intéressé à l'application de la méthode en incluant des intervalles de distances comme contraintes dans les calculs. Dans ce cas de figure, la méthode a réussi a reconstruire des structures références avec un RMSD inférieur à 5 Angstrom pour plus de la moitié des protéines cibles. En contre partie, le parcours complet de l'espace conformationnel n'a été possible que pour la plus petite protéine de l'ensemble des protéines étudiées. Pour la moitié des autres protéines, plus de 70% des atomes ont vu leurs positions échantillonnées. La qualité des structures obtenues a regressé en comparaison avec les simulations faites avec des distances exactes. En effet, seulement 53% des valeurs de phi et psi étaient localisées dans la zone 'core' du diagramme de Ramachandran, et le pourcentage d'atomes impliqués dans un clash stérique s'élevait jusqu'à 22% pour quelques protéines. Concernant le temps de calcul, le taux de génération de conformations a été déterminé pour chaque protéine cible, et il s'est avéré que globalement sa valeur etait compétitive par rapport aux valeurs des taux observables dans la littérature... / Structural biology has allowed us expand our knowledge of living organisms. It is defined as the investigation of the structure and function of biological systems at the molecular level. Studying a biomolecule's structure offers insight into its geometry, as angles and distances between the biomolecule's atoms are measured in order to determine the biomolecular structure. The values of these geometrical parameters may be obtained from biophysical techniques, such as X-ray crystallography or nuclear magnetic resonance (NMR) spectroscopy. One of the most used methods to calculate protein structures from geometric restraints is simulated annealing. This method does not guarantee an exhaustive sampling of protein conformational space, which is a shortcoming as one protein may adopt multiple functional conformations, and it is important to determine them exhaustively. In this PhD project, the efficiency of a new method - derived from operations research and computational geometry - is studied in order to answer this question: How does this method explore the conformational spaces of small proteins? This method - implemented within the iBPprot software framework - treats protein structure determination as a distance geometry problem, which the interval branch-and-prune algorithm tries to solve by the full exploration of its solutions space. The results obtained by iBPprot on a set of test proteins, with sizes ranging from 24 to 120 residues and with known structures, are analyzed here. Using short-range exact distance restraints, it was possible to rebuild the structure of all protein targets, and for many of them it was possible to exhaustively explore their conformational spaces. In practice, it is not always possible to obtain exact distance restraints from experiments. Therefore, this method was then tested with interval data restraints. In these cases, iBPprot permitted the sampling of the positions of more than 70% of the atoms constituting the protein backbone for most of the targets. Furthermore, conformations whose r.m.s. deviations closer than 6 Angstrom to the target ones were obtained during the conformational space exploration. The quality of the generated structures was satisfactory with respect to Ramachandran plots, but needs improvement because of the presence of steric clashes in some conformers. The runtime for most performed calculations was competitive with existing structure determination method...

Dentre as técnicas de mineração existentes encontra-se a associação, responsável por identificar relações que ocorrem no conjunto de dados. Embora a associação seja uma das técnicas mais utilizadas, a quantidade de padrões extraídos pode vir a sobrecarregar o usuário de tal maneira que encontrar algo interessante dentre a imensidão de padrões obtidos passa a ser um novo desafio. Para solucionar esse problema, uma grande parte dos trabalhos relacionados à associação está voltada a etapa de pós-processamento. Esses trabalhos geralmente propõem abordagens de pós-processamento que visam, segundo determinada estratégia, facilitar a busca pelos padrões interessantes ao domínio. Nos últimos anos, essas abordagens têm incluído no processo o conhecimento e/ou interesse do usuário sobre o domínio. Contudo, nas abordagens atualmente existentes, o usuário deve, por meio de algum formalismo descrever explicitamente seu conhecimento e/ou interesse, requerendo do usuário um tempo considerável, podendo levar, inclusive, a especificações incompletas e/ou incorretas. Além disso, na maioria das vezes, o usuário não tem ideia do que é provavelmente interessante, nem a partir de quais relações iniciar a busca. Nota-se, portanto, que um dos desafios dessas abordagens é considerar o conhecimento e/ou interesse do usuário. Além disso, é necessário considerar também o número de regras que o usuário analisará. A análise de regras feita por um especialista é custosa e, na maioria dos casos, o usuário quer explorar as regras geradas sem limitar a exploração ao conhecimento que ele já possui. Portanto, é importante que o usuário avalie o menor número de regras possível e, com base nessa avaliação, abordagens de pós-processamento consigam o auxiliar na busca pelas regras que ele poderá considerar interessante. Para tanto, é proposto neste trabalho que o pós-processamento seja tratado como um problema de classificação semissupervisionada transdutiva, uma vez que permite que o usuário rotule, considerando classes pré-definidas (por exemplo, \"Interessante\" ou \"Não Interessante\"), apenas algumas regras do conjunto a ser explorado para que todas as outras regras sejam automaticamente rotuladas. Além disso, por meio da definição dos rótulos de algumas regras, é possível capturar implicitamente o conhecimento e/ou interesse do usuário sobre o domínio. Para tanto, é necessário que as regras sejam modeladas de maneira a permitir: (a) selecionar as regras a serem rotuladas pelo usuário a fim de capturar implicitamente seu conhecimento e/ou interesse; (b) propagar os rótulos das regras já classificadas pelo usuário a todas as outras regras não rotuladas. Desse modo, neste trabalho, as regras foram modeladas via redes, uma vez que: (i) uma vasta quantidade de medidas de exploração de redes pode ser utilizada, em conjunto com as informações fornecidas pelo usuário, a fim de viabilizar o item (a); (ii) algoritmos de propagação de rótulos podem ser utilizados a fim de viabilizar o item (b). Diante do apresentado, ressalta-se que as contribuições deste trabalho estão na capacidade de se extrair o conhecimento e/ou interesse do usuário de acordo com as características da base de dados e direcionar sua exploração sem a necessidade de se definir previamente o que será explorado. Além disso, os resultados obtidos demonstram a capacidade da PARLP em direcionar o usuário para o conhecimento considerado interessante, reduzindo, para tanto, a quantidade de regras a serem exploradas. Por fim, este trabalho contribui também para demonstrar que é possível tratar o pós-processamento de regras de associação como um problema de propagação de rótulos. / One of the existing data mining techniques is association rules, responsible for identifying relationships that occur in the data set. Although the association rule is one of the most widely used techniques, the amount of extracted patterns can overload the user in such a way that finding interesting patterns among the large amount of obtained patterns becomes a challenge. To solve this problem, a large part of the association-related work is focused on the post-processing step. These works generally propose a post-processing approaches that, according to a certain strategy, aims facilitating the search for interesting patterns. Nowadays, approaches have included the user knowledge in the domain and / or interests on the process. However, in the current existing approaches, the user knowledge and/or interest must be explicitly described by some formalism, requiring a considerable time and may even lead to incomplete and / or incorrect specifications. In addition, the user has no idea what probably is interesting or which patterns to begin the searching. Notice that one of the challenges of these approaches is to consider the knowledge and / or user interest. In addition, consider the number of rules the user will examine is necessary. The analysis of the rules by an expert is expensive and, in most cases, the user wants to explore the rules generated without limiting exploration to the knowledge he already has. Therefore, the user evaluate the fewest amount of rules possible is important and, based on this assessment, the post-processing approaches be able to assist in the search for the rules that he may consider interesting. So, in this work is proposed that the post-processing is treated as a transductive semi supervised classification problem, since it allows the user to label some rules based on two predefined classes (e.g. \"interesting\"or \"not interesting\"), in a way that just a small amount of the rule set needs to be explored and all other association rules are automatically labeled. Furthermore, you can implicitly capture the knowledge and / or user interest in the domain by labeling some rules. Thus, the rules need to be modeled to allow: (a) select the rules to be labeled by the user to implicitly capture their knowledge and / or interest; (b) propagate the rules\' labels classified by the user to all not labeled rules. To do so, the rules were modeled via networks in this work, due to: (i) a large amount of network measures can be used in conjunction with the information provided by the user, to make item (a) possible; (ii) label propagation algorithms can be used in order to make item (b) possible. Therefore, we highlight that the contributions of this work are the ability to extract knowledge and / or user interest according to database characteristics and direct the user exploration without previously defining what will be explored. In addition, the results demonstrate that the proposed approach is able to direct the user to the knowledge considered interesting, reducing the amount of rules to be explored. Finally, this work also contributes to demonstrate that treat the post-processing of association rules as a problem of propagation of labels is possible.

Traditionally, burley tobacco has been harvested by hand because the green plant weight, volume, and leaf fragility make mechanical harvesting very challenging. This study examined possible ways to wilt a plant still standing in the field (termed ‘pre-wilting’) to reduce weight, volume, and leaf fragility. Several methods of pre-wilting burley tobacco plants in the field were explored including: root pruning, stalk girdling, freezing with liquid nitrogen, and burning. Experiments were conducted in three locations over three consecutive years during the tobacco harvest season. Leaf breaking angle, leaf moisture content and time-lapse photography were investigated as methods to quantify treatment effects on wilting. The time-lapse photography helped reveal that wilting was most prevalent during the late afternoon, and that wilted plants sometimes began to recover after more than five days, apparently due to root re-growth. Root pruning was the only mechanical means that caused witling reliably during the first two years of testing, and even then the results were somewhat inconsistent. During the third year, a high-clearance tobacco sprayer was modified with a hydraulically actuated coulter disc in order to root-prune a large number of subjects.

Rampant lateral gene transfer (LGT) among prokaryotes, hybridization in plants and other reticulate evolutionary processes invalidate typical phylogenetic tree models by violating the assumption that organisms only inherit genetic information from a single parent species. Comparing the different evolutionary histories of multiple genes is necessary to identify and assess these processes. In this work I develop efficient approximation and fixed-parameter algorithms for computing rooted maximum agreement forests (MAFs) and maximum acyclic agreement forests (MAAFs) of pairs of phylogenetic trees. Their sizes correspond to the subtree-prune-and-regraft (SPR) distance and the hybridization number of these pairs of trees, which are important measures of the dissimilarity of phylogenies used in studying reticulate evolution. Although these MAFs and MAAFs are NP-hard to compute, my fixed-parameter algorithms are practical because they scale exponentially with the computed distance rather than the size of the trees. I contribute efficient fixed-parameter algorithms for computing MAFs and MAAFs of two binary rooted trees and give the first efficient fixed-parameter and approximation algorithms for computing MAFs of two multifurcating rooted trees. My open-source implementation of the MAF algorithms is orders of magnitude faster than previous approaches, reducing the time required to compute SPR distances of 46 between trees of 144 species to fractions of a second whereas previous approaches required hours to compute SPR distances of 25. These fast MAF-based distance metrics enable the construction of supertrees to reconcile a collection of gene trees and rapid inference of LGT. Simulations demonstrate that supertrees minimizing the SPR distance are more accurate than other supertree methods under plausible rates of LGT. I constructed an SPR supertree from a phylogenomic dataset of 40,631 gene trees covering 244 genomes from several major bacterial phyla and inferred "highways" of gene transfer between these bacterial classes and genera; a small number of these highways connect distantly related genera and can highlight specific genes implicated in long-distance LGT. These fast MAF algorithms are thus practical and enable new analyses of reticulate evolution.

It has become well known that an evolutionary tree is inadequate to represent fully the history of life. Two possible ways of dealing with this are the rooted subtree prune and regraft distance between a pair of trees, which measures how different they are, and the slightly more biologically sound hybridisation number of a set of trees that attempts to determine the minimum number of hybrid events that must have occurred for a given set of evolutionary trees. When characterised via agreement forests both problems are, although NP hard, fixed parameter tractable---meaning the problem can be converted to a similar problem with a smaller input size. This thesis investigates ways of improving existing algorithms for calculating the minimum rooted subtree prune and regraft distance and hybridisation number for a pair or, in the latter case, set of trees. In both cases a technique is used that allows the problem to be rekernelised during the run of the program. Another, less effective method, is also looked at which finds the rooted subtree prune and regraft distance or hybridisation number solely on what cannot be contained within any agreement forest. Additionally the characterisation of the minimum rooted subtree prune and regraft distance via maximum agreement forests is extended to non-binary trees and the hybridisation number of a set of phylogenetic trees is extended to unrooted trees.

Despite being found in all presently sequenced genomes, the evolution of tandemly repeated sequences has only just begun to be understood. We can represent the duplication history of tandemly repeated sequences with duplication trees. Most phylogenetic techniques need to be modified to be used on duplication trees. Due to gene loss, it is not always possible to reconstruct the duplication history of a tandemly repeated sequence. This thesis addresses this problem by providing a polynomial-time locally optimal algorithm to reconstruct the duplication history of a tandemly repeated sequence in the presence of gene loss. Supertree methods cannot be directly applied to duplication trees. A polynomial-time algorithm that takes a forest of ordered phylogenies and looks for a super duplication tree is presented. If such a super duplication tree is found then the algorithm constructs the super duplication tree. However, the algorithm does not always find a super duplication tree when one exists. The SPR topological rearrangement in its current form cannot be used on duplication trees. The necessary modifications are made to an agreement forest so that the SPR operation can be used on duplication trees. This operation is called the duplication rooted subtree prune and regraft operation (DrSPR). The size of the DrSPR neighbourhood is calculated for simple duplication trees and the tree shapes that maximize and minimize this are given.

It has become well known that an evolutionary tree is inadequate to represent fully the history of life. Two possible ways of dealing with this are the rooted subtree prune and regraft distance between a pair of trees, which measures how different they are, and the slightly more biologically sound hybridisation number of a set of trees that attempts to determine the minimum number of hybrid events that must have occurred for a given set of evolutionary trees. When characterised via agreement forests both problems are, although NP hard, fixed parameter tractable---meaning the problem can be converted to a similar problem with a smaller input size. This thesis investigates ways of improving existing algorithms for calculating the minimum rooted subtree prune and regraft distance and hybridisation number for a pair or, in the latter case, set of trees. In both cases a technique is used that allows the problem to be rekernelised during the run of the program. Another, less effective method, is also looked at which finds the rooted subtree prune and regraft distance or hybridisation number solely on what cannot be contained within any agreement forest. Additionally the characterisation of the minimum rooted subtree prune and regraft distance via maximum agreement forests is extended to non-binary trees and the hybridisation number of a set of phylogenetic trees is extended to unrooted trees.