Kernel Methods for Tree Structured Data

Machine learning comprises a series of techniques for automatic extraction of meaningful information from large collections of noisy data. In many real world applications, data is naturally represented in structured form. Since traditional methods in machine learning deal with vectorial information, they require an a priori form of preprocessing. Among all the learning techniques for dealing with structured data, kernel methods are recognized to have a strong theoretical background and to be effective approaches. They do not require an explicit vectorial representation of the data in terms of features, but rely on a measure of similarity between any pair of objects of a domain, the kernel function. Designing fast and good kernel functions is a challenging problem. In the case of tree structured data two issues become relevant: kernel for trees should not be sparse and should be fast to compute. The sparsity problem arises when, given a dataset and a kernel function, most structures of the dataset are completely dissimilar to one another. In those cases the classifier has too few information for making correct predictions on unseen data. In fact, it tends to produce a discriminating function behaving as the nearest neighbour rule. Sparsity is likely to arise for some standard tree kernel functions, such as the subtree and subset tree kernel, when they are applied to datasets with node labels belonging to a large domain. A second drawback of using tree kernels is the time complexity required both in learning and classification phases. Such a complexity can sometimes prevents the kernel application in scenarios involving large amount of data. This thesis proposes three contributions for resolving the above issues of kernel for trees. A first contribution aims at creating kernel functions which adapt to the statistical properties of the dataset, thus reducing its sparsity with respect to traditional tree kernel functions. Specifically, we propose to encode the input trees by an algorithm able to project the data onto a lower dimensional space with the property that similar structures are mapped similarly. By building kernel functions on the lower dimensional representation, we are able to perform inexact matchings between different inputs in the original space. A second contribution is the proposal of a novel kernel function based on the convolution kernel framework. Convolution kernel measures the similarity of two objects in terms of the similarities of their subparts. Most convolution kernels are based on counting the number of shared substructures, partially discarding information about their position in the original structure. The kernel function we propose is, instead, especially focused on this aspect. A third contribution is devoted at reducing the computational burden related to the calculation of a kernel function between a tree and a forest of trees, which is a typical operation in the classification phase and, for some algorithms, also in the learning phase. We propose a general methodology applicable to convolution kernels. Moreover, we show an instantiation of our technique when kernels such as the subtree and subset tree kernels are employed. In those cases, Direct Acyclic Graphs can be used to compactly represent shared substructures in different trees, thus reducing the computational burden and storage requirements.

Impact of forest fragmentation and disturbance on the endangered tropical tree Prunus africana (Rosaceae)

Anthropogene Fragmentierung und Störung von Wäldern beeinflussen ökologische Prozesse. Darüber hinaus werden genetische Drift und Inzucht verstärkt und die Fitness von Populationen beeinträchtigt. Um die Einflüsse von Fragmentierung und Störung auf die Biodiversität und Prozesse in tropischen Wäldern zu ermitteln, habe ich im „Kakamega Forest“, West-Kenia, die Baumart Prunus africana genauer untersucht. Dabei lag der Fokus auf (i) der Frugivorengemeinschaft und Samenausbreitung, (ii) der Kleinsäugergemeinschaft im Kontext der Samenprädation und (iii) der genetische Populationsstruktur von Keimlingen und adulten Bäumen. Der Vergleich von Keimlingen mit adulten Bäumen ermöglicht es, Veränderungen im Genfluss zwischen Generationen festzustellen. Die Ergebnisse zeigten, dass im untersuchten Waldgebiet insgesamt 49 frugivore Arten (Affen und Vögel) vorkommen. Dabei lag die Gesamtartenzahl im zusammenhängenden Wald höher als in den isoliert liegenden Fragmenten. An den Früchten von P. africana konnten insgesamt 36 Arten fressend beobachtet werden. Hier jedoch wurden in Fragmenten eine leicht erhöhte Frugivorenzahl sowie marginal signifikant erhöhte Samenausbreitungsraten nachgewiesen. Der Vergleich von stark gestörten mit weniger gestörten Flächen zeigte eine höhere Gesamtartenzahl sowie eine signifikant höhere Frugivorenzahl in P. africana in stark gestörten Flächen. Entsprechend war die Samenausbreitungsrate in stark gestörten Flächen marginal signifikant erhöht. Diese Ergebnisse deuten darauf hin, dass die quantitative Samenausbreitung in fragmentierten und gestörten Flächen etwas erhöht ist und somit eine gewisse Artenredundanz besteht, die den Verlust einzelner Arten ausgleichen könnte. Prunus africana Samen, die auf dem Boden lagen, wurden hauptsächlich von einer Nagerart (Praomys cf. jacksonii) erbeutet. Dabei war in gestörten Waldbereichen eine tendenziell höhere Prädatoraktivität zu beobachten als in weniger gestörten. Zudem waren einzelne Samen im Gegensatz zu Samengruppen in gestörten Flächen signifikant höherem Prädationsdruck ausgesetzt. Diese Ergebnisse zeigen, dass Fragmentierung sowie anthropogene Störungen auf unterschiedliche Prozesse im Lebenszyklus eines tropischen Baumes gegensätzliche Effekte haben können. Eine Extrapolation von einem auf einen anderen Prozess kann somit nicht erfolgen. Die genetische Differenzierung der adulten Baumpopulationen war gering (FST = 0.026). Der Großteil ihrer Variation (~ 97 %) lag innerhalb der Populationen, was intensiven Genfluss in der Vergangenheit widerspiegelt. Die genetische Differenzierung der Keimlinge war etwas erhöht (FST = 0.086) und ~ 91 % ihrer Variation lag innerhalb der Populationen. Im Gegensatz zu den adulten Bäumen konnte ich für Keimlinge ein „Isolation-by-distance“-Muster feststellen. Somit sind erste Hinweise auf begrenzten Genfluss im Keimlingsstadium infolge von Fragmentierung gegeben. Obwohl die Momentaufnahmen im Freiland keine Abnahme in der Frugivorenzahl und Samenausbreitung von P. africana als Folge von Fragmentierung beobachten ließen, weisen die Ergebnisse der genetischen Studie auf einen bereits reduzierten Genaustausch zwischen den Populationen hin. Somit lässt sich feststellen, dass die Faktoren Fragmentierung und Störung genetische Diversität, ökologische Prozesse und Artendiversität in Wäldern jeweils auf unterschiedliche Weise beeinflussen. Um Konsequenzen derartiger Einflüsse folgerichtig abschätzen zu können, sind Studien auf unterschiedlichen Diversitätsebenen unabdingbar.

Study of Italian isolates of Alternaria spp.: molecular and morphological characterization and pathogenesis on apple tree

It was decided to carry out a morphological and molecular characterization of the Italian Alternaria isolatescollected from apple , and evaluate their pathogenicity and subsequently combining the data collected. The strain collection (174 isolates) was constructed by collecting material (received from extension service personnel) between June and August of 2007, 2008, and 2009. A Preliminary bioassays were performed on detached plant materials (fruit and leaf wounded and unwounded), belonging to the Golden cultivar, with two different kind of inoculation (conidial suspension and conidial filtrate). Symptoms were monitored daily and a value of pathogenicity score (P.S.) was assigned on the basis of the diameter of the necrotic area that developed. On the basis of the bioassays, the number of isolates to undergo further molecular analysis was restricted to a representative set of single spore strains (44 strains). Morphological characteristics of the colony and sporulation pattern were determined according to previous systematic work on small-spored Alternaria spp. (Pryor and Michaelides, 2002 and Hong et al., 2006). Reference strains (Alternaria alternata, Alternaria tenuissima, Alternaria arborescens and four Japanese strains of Alternaria alternata mali pathotype), used in the study were kindly provided by Prof. Barry Pryor, who allows a open access to his own fungal collection. Molecular characterization was performed combining and comparing different data sets obtained from distinct molecular approach: 1) investigation of specific loci and 2) fingerprinting based on diverse randomly selected polymorphic sites of the genome. As concern the single locus analysis, it was chosen to sequence the EndoPG partial gene and three anonymous region (OPA1-3, OPA2- and OPa10-2). These markers has revealed a powerful tool in the latter systematic works on small-spored Alternaria spp. In fact, as reported in literature small-spored Alternaria taxonomy is complicated due to the inability to resolve evolutionary relationships among the taxa because of the lack of variability in the markers commonly used in fungi systematic. The three data set together provided the necessary variation to establish the phylogenetic relationships among the Italian isolates of Alternaria spp. On Italian strains these markers showed a variable number of informative sites (ranging from 7 for EndoPg to 85 for OPA1-3) and the parsimony analysis produced different tree topologies all concordant to define A. arborescens as a mophyletic clade. Fingerprinting analysis (nine ISSR primers and eight AFLP primers combination) led to the same result: a monophyleic A. arborescens clade and one clade containing both A. tenuissima and the A. alternata strains. This first attempt to characterize Italian Alternaria species recovered from apple produced concordant results with what was already described in a similar phylogenetic study on pistachio (Pryor and Michaelides, 2002), on walnut and hazelnut (Hong et al., 2006), apple (Kang et al., 2002) and citurus (Peever et al., 2004). Together with these studies, this research demonstrates that the three morphological groups are widely distributed and occupy similar ecological niches. Furthermore, this research suggest that these Alternaria species exhibit a similar infection pattern despite the taxonomic and pathogenic differences. The molecular characterization of the pathogens is a fundamental step to understanding the disease that is spreading in the apple orchards of the north Italy. At the beginning the causal agent was considered as Alteraria alternata (Marshall and Bertagnoll, 2006). Their preliminary studies purposed a pathogenic system related to the synthesis of toxins. Experimental data of our bioassays suggest an analogous hypothesis, considering that symptoms could be induced after inoculating plant material with solely the filtrate from pathogenic strains. Moreover, positive PCR reactions using AM-toxin gene specific primers, designed for identification of apple infecting Alternaria pathovar, led to a hypothesis that a host specific toxin (toxins) were involved. It remains an intriguing challenge to discover or not if the agent of the “Italian disease” is the same of the one previously typified as Alternaria mali, casual agent of the apple blotch disease.

Frugivores, seed dispersal and tree regeneration along a human disturbance gradient in East African tropical rainforests

Samenausbreitung und Regeneration von Bäumen sind wichtig für den langfristigen Bestand von Baum- und Frugivorengemeinschaften in tropischen Regenwäldern. Zunehmende Rohdung und Degradation gefährden den Ablauf dieser mutualistischen Prozesse in diesem Ökosystem. Um den Einfluss von kleinräumiger menschlicher Störung auf die Frugivorengemeinschaft und die zentralen Ökosystemprozesse Samenausbreitung und Regeneration zu erforschen, habe ich 1) die Frugivorengemeinschaft und die Samenausbreitungsrate von Celtis durandii (Ulmaceae) und 2) den Zusammenhang zwischen Baumarten mit fleischigen Früchten, Frugivoren und der Etablierung von Keimlingen dieser Baumarten in unterschiedlich stark gestörten Flächen dreier ostafrikanischer tropischer Regenwälder untersucht. Insgesamt konnte ich 40 frugivore Vogel- und Primatenarten in den drei untersuchten Waldgebieten nachweisen. Auf gering gestörten Flächen wurden mehr Frugivore als auf stark gestörten Flächen aufgenommen. Auch die Beobachtungen an C. durandii ergaben mehr frugivore Besucher in Bäumen auf gering gestörten als auf stark gestörten Flächen. Dies führte zu einer marginal signifikant höheren Samenausbreitungsrate auf den gering gestörten Flächen. Diese Ergebnisse waren auf regionaler Ebene in allen drei untersuchten Wäldern konsistent. Dies zeigt, dass kleinräumige Störung einen umfassenderen negativen Einfluss auf Frugivore und ihre Funktion als Samenausbreiter hat als zuvor angenommen. Bei der Vegetationserfassung nahm ich 131 verschiedene Baumarten mit fleischigen Früchten in den drei Regenwäldern auf. Kleinräumige menschliche Störung erhöhte den Artenreichtum dieser Baumarten marginal signifikant, hatte jedoch keinen direkten Einfluss auf die Frugivorendichte und den Artenreichtum von Keimlingen dieser Baumarten. Der Artenreichtum von Baumarten mit fleischigen Früchten zeigte einen marginal signifikant positiven Einfluss auf die Frugivorendichte, allerdings nicht auf die Keimlinge. Allerdings führte die Dichte der Frugivoren zu signifikant erhöhtem Artenreichtum der Keimlinge. Folglich scheint kleinräumige Störung die Keimlingsetablierung indirekt durch erhöhten Baumartenreichtum und erhöhte Frugivorendichte zu beeinflussen. Die Frugivorendichte hatte einen größeren Einfluss auf die Waldregeneration als kleinräumige Störung und Baumartenreichtum. Demnach scheint kleinräumige menschliche Störung sowohl positive als auch negative Effekte auf Samenausbreitung und Regeneration zu haben. Somit sind weitere Studien notwendig, die den Einfluss von kleinräumiger menschlicher Störung auf Mutualismen tropischer Regenwälder aufklären.

Genetic dynamics across early life stages in the tropical tree Prunus africana (Rosaceae)

In many plant species, the genetic template of early life-stages is formed by animal-mediated pollination and seed dispersal and has profound impact on further recruitment and population dynamics. Understanding the impact of pollination and seed dispersal on genetic patterns is a central issue in plant population biology. In my thesis, I investigated (i) contemporary dispersal and gene flow distances as well as (ii) genetic diversity and spatial genetic structure (SGS) across subsequent recruitment stages in a population of the animal-pollinated and dispersed tree Prunus africana in Kakamega Forest, West Kenya. Using microsatellite markers and parentage analyses, I inferred distances of pollen dispersal (father-to-mother), seed dispersal/maternal gene flow (mother-to-offspring) as well as paternal gene flow (father-to-offspring) for four early life stages of the species (seeds and fruits, current year seedlings, seedlings ≤ 3yr, seedlings > 3yr). Distances of pollen and seed dispersal as well as paternal gene flow were significantly shorter than expected from the spatial arrangement of trees and sampling plots. They were not affected by the density of conspecific trees in the surrounding. At the propagule stage, mean pollen dispersal distances were considerably (23-fold) longer than seed dispersal distances, and paternal gene flow distances exceeded maternal gene flow by a factor of 25. Seed dispersal distances were remarkably restricted, potentially leading to a strong initial SGS. The initial genetic template created by pollination and seed dispersal was extensively altered during later recruitment stages. Potential Janzen-Connell effects led to markedly increasing distances between offspring and both parental trees in older life stages. This showed that distance and density-dependent mortality factors are not exclusively related to the mother tree, but also to the father. Across subsequent recruitment stages, the pollen to seed dispersal ratio and the paternal to maternal gene flow ratio dropped to 2.1 and 3.4, respectively, in seedlings > 3yr. The relative changes in effective pollen dispersal, seed dispersal, and paternal gene flow distances across recruitment stages elucidate the mechanisms affecting the contribution of the two processes pollen and seed dispersal to overall gene flow. Using the same six microsatellite loci, I analyzed genetic diversity and SGS across five life stages, from seed rain to adults. Levels of genetic diversity within the studied P. africana population were comparable to other Prunus species and did not vary across life stages. In congruence with the short seed dispersal distances, I found significant SGS in all life stages. SGS decreased from seed and early seedling stages to older juvenile stages, and it was higher in adults than in late juveniles of the next generation. A comparison of the data with direct assessments of contemporary gene flow patterns indicate that distance- or density-dependent mortality, potentially due to Janzen-Connell effects, led to the initial decrease in SGS. Intergeneration variation in SGS could have been driven by variation in demographic processes, the effect of overlapping generations, and local selection processes. Overall, my study showed that complex sequential processes during recruitment contribute to the spatial genetic structure of tree populations. It highlights the importance of a multistage perspective for a comprehensive understanding of the impact of animal-mediated pollen and seed dispersal on spatial population dynamics and genetic patterns of trees.

Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Starch distribution in pear tree organs in relation to training systems, rootstocks and fruit quality

Starch is the main form in which plants store carbohydrates reserves, both in terms of amounts and distribution among different plant species. Carbohydrates are direct products of photosynthetic activity, and it is well know that yield efficiency and production are directly correlated to the amount of carbohydrates synthesized and how these are distributed among vegetative and reproductive organs. Nowadays, in pear trees, due to the modernization of orchards, through the introduction of new rootstocks and the development of new training systems, the understanding and the development of new approaches regarding the distribution and storage of carbohydrates, are required. The objective of this research work was to study the behavior of carbohydrate reserves, mainly starch, in different pear tree organs and tissues: i.e., fruits, leaves, woody organs, roots and flower buds, at different physiological stages during the season. Starch in fruit is accumulated at early stages, and reached a maximum concentration during the middle phase of fruit development; after that, its degradation begins with a rise in soluble carbohydrates. Moreover, relationships between fruit starch degradation and different fruit traits, soluble sugars and organic acids were established. In woody organs and roots, an interconversion between starch and soluble carbohydrates was observed during the dormancy period that confirms its main function in supporting the growth and development of new tissues during the following spring. Factors as training systems, rootstocks, types of bearing wood, and their position on the canopy, influenced the concentrations of starch and soluble carbohydrates at different sampling dates. Also, environmental conditions and cultural practices must be considered to better explain these results. Thus, a deeper understanding of the dynamics of carbohydrates reserves within the plant could provide relevant information to improve several management practices to increase crop yield efficiency.

Wet bioadhesion in tree frogs

Viele Tiere wie etwa Geckos oder Laubfrösche können mittels ihrer Haftscheiben an Oberflächen kleben. Diese Haftscheiben ermöglichen es den Tieren, sich während ihrerrnFortbewegung an Oberflächen anzuheften und wieder zu lösen unabhängig von denrnvorherrschenden Umweltbedingungen. Frösche besitzen mikro- und nanostrukturierternsowie charakteristisch geformte Haftscheiben an Finger- und Zehenenden. Ihre besonderernevolutionäre Errungenschaft, sich stark und zugleich reversibel in sowohl trockenen alsrnauch feuchten Umgebungen anzuhaften, hat die Wissenschaft zur Nachahmung und Untersuchungrndieser Strukturen inspiriert. Zum besseren Verständnis der Mechanismen vonrnAnhaftung und Loslösung bei Laubfröschen wurden weiche, elastische und mikrostrukturierternOberflächen hergestellt, indem PDMS (Polydimethylsiloxan) auf einer Siliziummaskernmit Hexagonstruktur aufgetragen und vernetzt wurde. Dadurch wurden Anordnungenrnvon hexagonalen Mikrosäulen mit spezifischen geometrischen Eigenschaften undrnunterschiedlichen Kontaktgeometrien (normale, flache Form, T-Form und konkave Formrnder Säulenenden) erhalten. Um den Einfluss der van-der-Waals, hydrodynamischen,rnKapillar-und Adhäsionskräfte zu verstehen, wurden verschiedene experimentelle Ansätzernverfolgt: Die auf eine einzelne Säule wirkenden Adhäsionskräfte wurden mittelsrnRasterkraftmikroskopie gemessen. Dazu wurden speziell hergestellte kolloidale Sensorenrnverwendet. Diese Experimente wurden sowohl mit als auch ohne Flüssigkeitsfilm auf derrnSäule durchgeführt. Die Ergebnisse zeigten den Beitrag von Kapillarkraft und direktenrnKontaktkräften zur Adhäsionskraft bei Vorliegen eines Flüssigkeitsfilms. Die Adhäsionrnfiel umso größer aus, je weniger Flüssigkeit zwischen Sensor und Säule vorhanden war.rnIm Falle einer trockenen Adhäsion zeigte die Säule mit T-Form die höchste Adhäsion. Darndie Haftscheiben der Laubfrösche weich sind, können sie dynamisch ihre Form ändern,rnwas zu einer Änderung der hydrodynamischen Kraft zwischen Scheibe und Oberflächernführt. Der Einfluss der Oberflächenverformbarkeit auf die hydrodynamische Kraft wurderndaher am Modellsystem einer Kugel untersucht, welche sich einer weichen und ebenenrnOberfläche annähert. Dieses System wurde sowohl theoretisch über die Simulation finiterrnElemente als auch experimentell über die Messung mit kolloidalen Sonden untersucht.rnSowohl experimentelle Ergebnisse als auch die Simulationen ergaben eine Abnahme derrnhydrodynamischen Kraft bei Annäherung des kolloidalen Sensors an eine weiche undrnelastische Oberfläche. Beim Entfernen der Sensors von der Oberfläche verstärkte sichrndie hydrodynamische Anziehungskraft. Die Kraft, die zur Trennung eines Partikels von einer Oberfläche in Flüssigkeit notwendig ist, ist für weiche und elastischen Oberflächenrngrößer als für harte Oberflächen. In Bezug zur Bioadhäsion bei Laubfröschen konnternfestgestellt somit festgestellt werden, dass sich der hydrodynamische Anteil zur feuchtenrnBioadhäsion aufgrund der weichen Oberfläche erhöht. Weiterhin wurde der Einflussrndes Aspektverhältnisses der Säulen auf die Reibungskraft mittels eines kolloidalen Sensorsrnuntersucht. Gestreckte Säulen zeigten dabei eine höhere Reibung im Vergleich zu.rnSäulen mit einem gestreckten Hexagon als Querschnitt.

Influence of micro-site conditions and environmental gradients on tree-ring based climate reconstructions

Tree-ring chronologies are a powerful natural archive to reconstruct summer temperature variations of the late Holocene with an annual resolution. To develop these long-term proxy records tree-ring series are commonly extended back in time by combining samples from living trees with relict dead material preserved onshore or in lakes. Former studies showed that low frequency variations in such reconstructions can be biased if the relict and recent material is from different origins. A detailed analysis of the influence of various ecological (micro-) habitats representing the recent part is required to estimate potential errors in temperature estimates. The application of collective detrending methods, that comprise absolute growth rates, can produce errors in climate reconstructions and results in an underestimation of past temperatures. The appearance of these kind of micro-site effects is a wide-spread phenomenon that takes place all over Fennoscandia. Future research in this key region for dendroclimatology should take this issue into account. Especially the higher climate response at the lakeshore site is interesting to achieve smaller uncertainties when a tree-ring series is transformed to temperature anomalies. For new composite chronologies the main aim should be to minimize potential biases and this includes also micro-site effects.

Recruitment dynamics of the grove-dominant tree Microberlinia bisulcata in African rain forest: extending the light response versus adult longevity trade-off concept

In groves of ectomycorrhizal caesalpiniaceous species in the Atlantic coastal forest of Central Africa the dominant tree Microberlinia bisulcata, which is shade-intolerant as a seedling but highly light-responding as a sapling, shows very limited regeneration. M. bisulcata saplings were mapped in an 82.5-ha plot at Korup and found to be located significantly far (>40 m) away from adults, a result confirmed by direct testing in a second 56-ha plot. Sapling growth over 6 years, the distribution of newly emerging seedlings around adults, recruitment of saplings in a large opening and the outward extent of seedlings at the grove edge were also investigated. Two processes appear to have been operating: (1) a very strong and consistent restriction of the very numerous seedlings establishing after masting close to adults, and (2) a strong but highly spatially variable promotion of distant survivors by increased light from the deaths of large trees of species other than M. bisulcata (which itself has very low mortality rate). This leads to an apparent escape-from-adults effect. To maintain saplings in the shade between multiple short periods of release ectomycorrhizal connections to other co-occurring caesalp species may enable a rachet-type mechanism. The recorded sapling dynamics currently contribute an essential part of the long-term cycling of the groves. M. bisulcata is an interesting example of an important group of tropical trees, particularly in Africa, which are both highly light-demanding when young yet capable also of forming very large forest emergents. To more comprehensively explain tropical tree responses, the case is made for adding a new dimension to the trade-off concept of early tree light-response versus adult longevity.