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.

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.