Efficient subsequence alignment of time series

Zeitreihen sind allgegenwärtig. Die Erfassung und Verarbeitung kontinuierlich gemessener Daten ist in allen Bereichen der Naturwissenschaften, Medizin und Finanzwelt vertreten. Das enorme Anwachsen aufgezeichneter Datenmengen, sei es durch automatisierte Monitoring-Systeme oder integrierte Sensoren, bedarf außerordentlich schneller Algorithmen in Theorie und Praxis. Infolgedessen beschäftigt sich diese Arbeit mit der effizienten Berechnung von Teilsequenzalignments. Komplexe Algorithmen wie z.B. Anomaliedetektion, Motivfabfrage oder die unüberwachte Extraktion von prototypischen Bausteinen in Zeitreihen machen exzessiven Gebrauch von diesen Alignments. Darin begründet sich der Bedarf nach schnellen Implementierungen. Diese Arbeit untergliedert sich in drei Ansätze, die sich dieser Herausforderung widmen. Das umfasst vier Alignierungsalgorithmen und ihre Parallelisierung auf CUDA-fähiger Hardware, einen Algorithmus zur Segmentierung von Datenströmen und eine einheitliche Behandlung von Liegruppen-wertigen Zeitreihen.rnrnDer erste Beitrag ist eine vollständige CUDA-Portierung der UCR-Suite, die weltführende Implementierung von Teilsequenzalignierung. Das umfasst ein neues Berechnungsschema zur Ermittlung lokaler Alignierungsgüten unter Verwendung z-normierten euklidischen Abstands, welches auf jeder parallelen Hardware mit Unterstützung für schnelle Fouriertransformation einsetzbar ist. Des Weiteren geben wir eine SIMT-verträgliche Umsetzung der Lower-Bound-Kaskade der UCR-Suite zur effizienten Berechnung lokaler Alignierungsgüten unter Dynamic Time Warping an. Beide CUDA-Implementierungen ermöglichen eine um ein bis zwei Größenordnungen schnellere Berechnung als etablierte Methoden.rnrnAls zweites untersuchen wir zwei Linearzeit-Approximierungen für das elastische Alignment von Teilsequenzen. Auf der einen Seite behandeln wir ein SIMT-verträgliches Relaxierungschema für Greedy DTW und seine effiziente CUDA-Parallelisierung. Auf der anderen Seite führen wir ein neues lokales Abstandsmaß ein, den Gliding Elastic Match (GEM), welches mit der gleichen asymptotischen Zeitkomplexität wie Greedy DTW berechnet werden kann, jedoch eine vollständige Relaxierung der Penalty-Matrix bietet. Weitere Verbesserungen umfassen Invarianz gegen Trends auf der Messachse und uniforme Skalierung auf der Zeitachse. Des Weiteren wird eine Erweiterung von GEM zur Multi-Shape-Segmentierung diskutiert und auf Bewegungsdaten evaluiert. Beide CUDA-Parallelisierung verzeichnen Laufzeitverbesserungen um bis zu zwei Größenordnungen.rnrnDie Behandlung von Zeitreihen beschränkt sich in der Literatur in der Regel auf reellwertige Messdaten. Der dritte Beitrag umfasst eine einheitliche Methode zur Behandlung von Liegruppen-wertigen Zeitreihen. Darauf aufbauend werden Distanzmaße auf der Rotationsgruppe SO(3) und auf der euklidischen Gruppe SE(3) behandelt. Des Weiteren werden speichereffiziente Darstellungen und gruppenkompatible Erweiterungen elastischer Maße diskutiert.

Der Carrier DcuB als zweiter Sensor des Zweikomponentensystems DcuSR in Escherichia coli

Escherichia coli kann C4-Dicarboxylate und andere Carbonsäuren als Substrate für den aeroben und anaeroben Stoffwechsel nutzen. Die Anwesenheit von C4-Dicarboxylaten im Außenmedium wird über das Zweikomponentensystem DcuSR, bestehend aus der membranständigen Sensorkinase DcuS und dem cytoplasmatischen Responseregulator DcuR, erkannt. Die Bindung von C4-Dicarboxylaten an die periplasmatische Domäne von DcuS führt zu einer Induktion der Zielgene. Hierzu zählen die Gene für den anaeroben Fumarat/Succinat-Antiporter DcuB (dcuB), die anaerobe Fumarase (fumB) und die Fumaratreduktase (frdABCD). Unter aeroben Bedingungen stimuliert DcuSR die Expression des dctA Gens, das für den aeroben C4-Dicarboxylat-Carrier DctA kodiert. Für den Carrier DcuB konnte eine regulatorische Funktion bei der Expression der DcuSR-regulierten Gene gezeigt werden. Die Inaktivierung des dcuB Gens führte bereits ohne Fumarat zu einer maximalen Expression einer dcuB´-´lacZ Reportergenfusion und anderer DcuSR-abhängiger Gene. Diese Stimulierung erfolgte nur in einem dcuS-positiven Hintergrund. DcuB unterscheidet sich damit von den alternativen Carriern DcuA und DcuC, die diesen Effekt nicht zeigten. Mithilfe ungerichteter Mutagenese wurden DcuB-Punktmutanten hergestellt (Thr394Ile und Asp398Asn), die eine Geninduktion verursachten, aber eine intakte Transportfunktion besaßen. Dies zeigt, dass der regulatorische Effekt von DcuB unabhängig von dessen Transportfunktion ist. Durch gerichtete Mutagenese wurde die Funktion einer Punktmutation (Thr394) näher charakterisiert. Es werden zwei Modelle zur Membrantopologie von DcuB und der Lage der Punktmutationen im Protein vorgestellt. Da DcuB seine regulatorische Funktion über eine Interaktion mit DcuS vermitteln könnte, wurden mögliche Wechselwirkungen zwischen DcuB und DcuS als auch DcuR mithilfe von Two-Hybrid-Systemen untersucht. Für biochemische Untersuchungen von DcuB wurde außerdem die Expression des Proteins in vivo und in vitro versucht. Unter aeroben Bedingungen beeinflusst der C4-Dicarboxylat-Carrier DctA die Expression der DcuSR-abhängigen Gene. Eine Mutation des dctA Gens bewirkte eine stärkere Expression einer dctA´-´lacZ Reportergenfusion im Vergleich zum Wildtyp. Diese Expression nahm in einem dcuS-negativen Hintergrund ab, die Succinat-abhängige Induktion blieb jedoch erhalten. Unter anaeroben Bedingungen kann das dctA Gen auch durch Inaktivierung von DcuB induziert werden. Es wird ein Modell vorgestellt, das die Beteiligung beider Carrier an der DcuSR-abhängigen Regulation erklärt.

Partial melting within the lower crust – Constraints from bulk rock geochemical data and trace element mineral analyses of granulites and migmatites from Central Finland

This PhD thesis concerns geochemical constraints on recycling and partial melting of Archean continental crust. A natural example of such processes was found in the Iisalmi area of Central Finland. The rocks from this area are Middle to Late Archean in age and experienced metamorphism and partial melting between 2.7-2.63 Ga. The work is based on extensive field work. It is furthermore founded on bulk rock geochemical data as well as in-situ analyses of minerals. All geochemical data were obtained at the Institute of Geosciences, University of Mainz using X-ray fluorescence, solution ICP-MS and laser ablation-ICP-MS for bulk rock geochemical analyses. Mineral analyses were accomplished by electron microprobe and laser ablation ICP-MS. Fluid inclusions were studied by microscope on a heating-freezing-stage at the Geoscience Center, University Göttingen. Part I focuses on the development of a new analytical method for bulk rock trace element determination by laser ablation-ICP-MS using homogeneous glasses fused from rock powder on an Iridium strip heater. This method is applicable for mafic rock samples whose melts have low viscosities and homogenize quickly at temperatures of ~1200°C. Highly viscous melts of felsic samples prevent melting and homogenization at comparable temperatures. Fusion of felsic samples can be enabled by addition of MgO to the rock powder and adjustment of melting temperature and melting duration to the rock composition. Advantages of the fusion method are low detection limits compared to XRF analyses and avoidance of wet-chemical processing and use of strong acids as in solution ICP-MS as well as smaller sample volumes compared to the other methods. Part II of the thesis uses bulk rock geochemical data and results from fluid inclusion studies for discrimination of melting processes observed in different rock types. Fluid inclusion studies demonstrate a major change in fluid composition from CO2-dominated fluids in granulites to aqueous fluids in TTG gneisses and amphibolites. Partial melts were generated in the dry, CO2-rich environment by dehydration melting reactions of amphibole which in addition to tonalitic melts produced the anhydrous mineral assemblages of granulites (grt + cpx + pl ± amph or opx + cpx + pl + amph). Trace element modeling showed that mafic granulites are residues of 10-30 % melt extraction from amphibolitic precursor rocks. The maximum degree of melting in intermediate granulites was ~10 % as inferred from modal abundances of amphibole, clinopyroxene and orthopyroxene. Carbonic inclusions are absent in upper-amphibolite facies migmatites whereas aqueous inclusion with up to 20 wt% NaCl are abundant. This suggests that melting within TTG gneisses and amphibolites took place in the presence of an aqueous fluid phase that enabled melting at the wet solidus at temperatures of 700-750°C. The strong disruption of pre-metamorphic structures in some outcrops suggests that the maximum amount of melt in TTG gneisses was ~25 vol%. The presence of leucosomes in all rock types is taken as the principle evidence for melt formation. However, mineralogical appearance as well as major and trace element composition of many leucosomes imply that leucosomes seldom represent frozen in-situ melts. They are better considered as remnants of the melt channel network, e.g. ways on which melts escaped from the system. Part III of the thesis describes how analyses of minerals from a specific rock type (granulite) can be used to determine partition coefficients between different minerals and between minerals and melt suitable for lower crustal conditions. The trace element analyses by laser ablation-ICP-MS show coherent distribution among the principal mineral phases independent of rock composition. REE contents in amphibole are about 3 times higher than REE contents in clinopyroxene from the same sample. This consistency has to be taken into consideration in models of lower crustal melting where amphibole is replaced by clinopyroxene in the course of melting. A lack of equilibrium is observed between matrix clinopyroxene / amphibole and garnet porphyroblasts which suggests a late stage growth of garnet and slow diffusion and equilibration of the REE during metamorphism. The data provide a first set of distribution coefficients of the transition metals (Sc, V, Cr, Ni) in the lower crust. In addition, analyses of ilmenite and apatite demonstrate the strong influence of accessory phases on trace element distribution. Apatite contains high amounts of REE and Sr while ilmenite incorporates about 20-30 times higher amounts of Nb and Ta than amphibole. Furthermore, trace element mineral analyses provide evidence for magmatic processes such as melt depletion, melt segregation, accumulation and fractionation as well as metasomatism having operated in this high-grade anatectic area.

Oligomerisation, localisation and interaction of the sensor histidine kinases DcuS and CitA in Escherichia coli

The two-component system DcuSR of Escherichia coli regulates gene expression of anaerobic fumarate respiration and aerobic C4-dicarboxylate uptake. C4-dicarboxylates and citrate are perceived by the periplasmic domain of the membrane-integral sensor histidine kinase DcuS. The signal is transduced across the membrane by phosphorylation of DcuS and of the response regulator DcuR, resulting in activation of DcuR and transcription of the target genes.rnIn this work, the oligomerisation of full-length DcuS was studied in vivo and in vitro. DcuS was genetically fused to derivatives of the green fluorescent protein (GFP), enabling fluorescence resonance energy transfer (FRET) measurements to detect protein-protein interactions in vivo. FRET measurements were also performed with purified His6-DcuS after labelling with fluorescent dyes and reconstitution into liposomes to study oligomerisation of DcuS in vitro. In vitro and in vivo fluorescence resonance energy transfer showed the presence of oligomeric DcuS in the membrane, which was independent of the presence of effector. Chemical crosslinking experiments allowed clear-cut evaluation of the oligomeric state of DcuS. The results showed that detergent-solubilised His6-DcuS was mainly monomeric and demonstrated the presence of tetrameric DcuS in proteoliposomes and in bacterial membranes.rnThe sensor histidine kinase CitA is part of the two-component system CitAB of E. coli, which is structurally related to DcuSR. CitAB regulates gene expression of citrate fermentation in response to external citrate. The sensor kinases DcuS and CitA were fused with an enhanced variant of the yellow fluorescent protein (YFP) and expressed in E. coli under the control of an arabinose-inducible promoter. The subcellular localisation of DcuS-YFP and CitA-YFP within the cell membrane was studied by means of confocal laser fluorescence microscopy. Both fusion proteins were found to accumulate at the cell poles. The polar accumulation was slightly increased in the presence of the stimulus fumarate or citrate, respectively, but independent of the expression level of the fusion proteins. Cell fractionation demonstrated that polar accumulation was not related to inclusion bodies formation. The degree of polar localisation of DcuS-YFP was similar to that of the well-characterised methyl-accepting chemotaxis proteins (MCPs), but independent of their presence. To enable further investigations on the function of the polar localisation of DcuS under physiological conditions, the sensor kinase was genetically fused to the flavin-based fluorescent protein Bs2 which shows fluorescence under aerobic and anaerobic conditions. The resulting dcuS-bs2 gene fusion was inserted into the chromosome of various E. coli strains.rnFurthermore, a protein-protein interaction between the related sensor histidine kinases DcuS and CitA, regulating common metabolic pathways, was detected via expression studies under anaerobic conditions in the presence of citrate and by in vivo FRET measurements.

The NreABC system of Staphylococcus carnosus combines nitrate and oxygen sensing by an NreA,NreB sensor complex

Staphylococcus carnosus is a facultative anaerobic bacterium which features the cytoplasmic NreABC system. It is necessary for regulation of nitrate respiration and the nitrate reductase gene narG in response to oxygen and nitrate availability. NreB is a sensor kinase of a two-component system and represents the oxygen sensor of the system. It binds an oxygen labile [4Fe-4S]2+ cluster under anaerobic conditions. NreB autophosphorylates and phosphoryl transfer activates the response regulator NreC which induces narG expression. The third component of the Nre system is the nitrate receptor NreA. In this study the role of the nitrate receptor protein NreA in nitrate regulation and its functional and physiological effect on oxygen regulation and interaction with the NreBC two-component system were detected. In vivo, a reporter gene assay for measuring expression of the NreABC regulated nitrate reductase gene narG was used for quantitative evaluation of NreA function. Maximal narG expression in wild type S. carnosus required anaerobic conditions and the presence of nitrate. Deletion of nreA allowed expression of narG under aerobic conditions, and under anaerobic conditions nitrate was no longer required for maximal induction. This indicates that NreA is a nitrate regulated inhibitor of narG expression. Purified NreA and variant NreA(Y95A) inhibited the autophosphorylation of anaerobic NreB in part and completely, respectively. Neither NreA nor NreA(Y95A) stimulated dephosphorylation of NreB-phosphate, however. Inhibition of phosphorylation was relieved completely when NreA with bound nitrate (NreA•[NO3-]) was used. The same effects of NreA were monitored with aerobically isolated Fe-S-less NreB, which indicates that NreA does not have an influence on the iron-sulfur cluster of NreB. In summary, the data of this study show that NreA interacts with the oxygen sensor NreB and controls its phosphorylation level in a nitrate dependent manner. This modulation of NreB-function by NreA and nitrate results in nitrate/oxygen co-sensing by an NreA/NreB sensory unit. It transmits the regulatory signal from oxygen and nitrate in a joint signal to target promoters. Therefore, nitrate and oxygen regulation of nitrate dissimilation follows a new mode of regulation not present in other facultative anaerobic bacteria.

A new information fusion method for land-use classification using high resolution satellite imagery

Satellite image classification involves designing and developing efficient image classifiers. With satellite image data and image analysis methods multiplying rapidly, selecting the right mix of data sources and data analysis approaches has become critical to the generation of quality land-use maps. In this study, a new postprocessing information fusion algorithm for the extraction and representation of land-use information based on high-resolution satellite imagery is presented. This approach can produce land-use maps with sharp interregional boundaries and homogeneous regions. The proposed approach is conducted in five steps. First, a GIS layer - ATKIS data - was used to generate two coarse homogeneous regions, i.e. urban and rural areas. Second, a thematic (class) map was generated by use of a hybrid spectral classifier combining Gaussian Maximum Likelihood algorithm (GML) and ISODATA classifier. Third, a probabilistic relaxation algorithm was performed on the thematic map, resulting in a smoothed thematic map. Fourth, edge detection and edge thinning techniques were used to generate a contour map with pixel-width interclass boundaries. Fifth, the contour map was superimposed on the thematic map by use of a region-growing algorithm with the contour map and the smoothed thematic map as two constraints. For the operation of the proposed method, a software package is developed using programming language C. This software package comprises the GML algorithm, a probabilistic relaxation algorithm, TBL edge detector, an edge thresholding algorithm, a fast parallel thinning algorithm, and a region-growing information fusion algorithm. The county of Landau of the State Rheinland-Pfalz, Germany was selected as a test site. The high-resolution IRS-1C imagery was used as the principal input data.