Effiziente und robuste, feature-basierte Wiedererkennung langer Zeitreihen in großen Datenbanken

Die Materialverfolgung gewinnt in der Metallindustrie immer mehr an Bedeutung:rnEs ist notwendig, dass ein Metallband im Fertigungsprozess ein festgelegtes Programm durchläuft - erst dann ist die Qualität des Endprodukts garantiert. Die bisherige Praxis besteht darin, jedem Metallband eine Nummer zuzuordnen, mit der dieses Band beschriftet wird. Bei einer tagelangen Lagerung der Bänder zwischen zwei Produktionsschritten erweist sich diese Methode als fehleranfällig: Die Beschriftungen können z.B. verloren gehen, verwechselt, falsch ausgelesen oder unleserlich werden. 2007 meldete die iba AG das Patent zur Identifikation der Metallbänder anhand ihres Dickenprofils an (Anhaus [3]) - damit kann die Identität des Metallbandes zweifelsfrei nachgewiesen werden, eine zuverlässige Materialverfolgung wurde möglich.Es stellte sich jedoch heraus, dass die messfehlerbehafteten Dickenprofile, die als lange Zeitreihen aufgefasst werden können, mit Hilfe von bisherigen Verfahren (z.B. L2-Abstandsminimierung oder Dynamic Time Warping) nicht erfolgreich verglichen werden können.Diese Arbeit stellt einen effizienten feature-basierten Algorithmus zum Vergleichrnzweier Zeitreihen vor. Er ist sowohl robust gegenüber Rauschen und Messausfällen als auch invariant gegenüber solchen Koordinatentransformationen der Zeitreihen wie Skalierung und Translation. Des Weiteren sind auch Vergleiche mit Teilzeitreihen möglich. Unser Framework zeichnet sich sowohl durch seine hohe Genauigkeit als auch durch seine hohe Geschwindigkeit aus: Mehr als 99.5% der Anfragen an unsere aus realen Profilen bestehende Testdatenbank werden richtig beantwortet. Mit mehreren hundert Zeitreihen-Vergleichen pro Sekunde ist es etwa um den Faktor 10 schneller als die auf dem Gebiet der Zeitreihenanalyse etablierten Verfahren, die jedoch nicht im Stande sind, mehr als 90% der Anfragen korrekt zu verarbeiten. Der Algorithmus hat sich als industrietauglich erwiesen. Die iba AG setzt ihn in einem weltweit einzigartigen dickenprofilbasierten Überwachungssystemrnzur Materialverfolgung ein, das in ersten Stahl- und Aluminiumwalzwerkenrnbereits erfolgreich zum Einsatz kommt.

Beiträge zur Steuerung und Analyse von technischen Bearbeitungssystemen mit Methoden der nichtlinearen Zeitreihenanalyse

Die Nichtlineare Zeitreihenanalyse konnte in den letzten Jahren im Rahmen von Laborexperimenten ihre prinzipelle Brauchbarkeit beweisen. Allerdings handelte es sich in der Regel um ausgewählte oder speziell konstruierte nichtlineare Systeme. Sieht man einmal von der Überwachung von Prozessen und Produkten ab, so sind Anwendungen auf konkrete, vorgegebene dynamische Probleme im industriellen Bereich kaum bekannt geworden. Ziel dieser Arbeit war es, an Hand von zwei Problemen aus der technischen Praxis zu untersuchen, ob die Anwendung des kanonischen Schemas der Nichtlinearen Zeitreihenanalyse auch dort zu brauchbaren Resultaten führt oder ob Modifikationen (Vereinfachungen oder Erweiterungen) notwendig werden. Am Beispiel der Herstellung von optischen Oberflächen durch Hochpräzisionsdrehbearbeitung konnte gezeigt werden, daß eine aktive Störungskompensation in Echtzeit mit einem speziell entwickelten nichtlinearen Vorhersagealgorithmus möglich ist. Standardverfahren der Nichtlinearen Zeitreihenanalyse beschreiten hier den allgemeinen, aber sehr aufwendigen Weg über eine möglichst vollständige Phasenraumrekonstruktion. Das neue Verfahren verzichtet auf viele der kanonischen Zwischenschritte. Dies führt zu einererheblichen Rechenzeitersparnis und zusätzlich zu einer wesentlich höheren Stabilität gegenüber additivem Meßrauschen. Mit den berechneten Vorhersagen der unerwünschten Maschinenschwingungen wurde eine Störungskompensation realisiert, die die Oberflächengüte des bearbeiteten Werkstücks um 20-30% verbesserte. Das zweite Beispiel betrifft die Klassifikation von Körperschallsignalen, die zur Überwachung von Zerspansprozessen gemessen werden. Diese Signale zeigen, wie auch viele andere Prozesse im Bereich der Produktion, ein hochgradig nichtstationäres Verhalten. Hier versagen die Standardverfahren der Nichtlinearen Datenanalyse, die FT- bzw. AAFT-Surrogate benutzen. Daher wurde eine neue Klasse von Surrogatdaten zum Testen der Nullhypothese nichtstationärer linearer stochastischer Prozesse entwickelt, die in der Lage ist, zwischen deterministischen nichtlinear chaotischen und stochastischen linearen nichtstationären Zeitreihen mit change points zu unterscheiden. Damit konnte gezeigt werden, daß die untersuchten Köperschallsignale sich statistisch signifikant einer nichtstationären stochastischen Folge von einfachen linearen Prozessen zuordnen lassen und eine Interpretation als nichtlineare chaotische Zeitreihe nicht erforderlich ist.

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.

Informationsgehalt von ERS-1/-2 SAR-Daten zur Erfassung der Arteninventare und des Zustandes landwirtschaftlich genutzter Böden und Vegetation

Auf einer drei Anbauperioden umfassenden Ground Truth Datenbasis wird der Informationsgehalt multitemporaler ERS-1/-2 Synthetic Aperture Radar (SAR) Daten zur Erfassung der Arteninventare und des Zustandes landwirtschaftlich genutzter Böden und Vegetation in Agrarregionen Bayerns evaluiert.Dazu wird ein für Radardaten angepaßtes, multitemporales, auf landwirtschaftlichen Schlägen beruhendes Klassifizierungsverfahren ausgearbeitet, das auf bildstatistischen Parametern der ERS-Zeitreihen beruht. Als überwachte Klassifizierungsverfahren wird vergleichend der Maximum-Likelihood-Klassifikator und ein Neuronales-Backpropagation-Netz eingesetzt. Die auf Radarbildkanälen beruhenden Gesamtgenauigkeiten variieren zwischen 75 und 85%. Darüber hinaus wird gezeigt, daß die interferometrische Kohärenz und die Kombination mit Bildkanälen optischer Sensoren (Landsat-TM, SPOT-PAN und IRS-1C-PAN) zur Verbesserung der Klassifizierung beitragen. Gleichermaßen können die Klassifizierungsergebnisse durch eine vorgeschaltete Grobsegmentierung des Untersuchungsgebietes in naturräumlich homogene Raumeinheiten verbessert werden. Über die Landnutzungsklassifizierung hinaus, werden weitere bio- und bodenphysikalische Parameter aus den SAR-Daten anhand von Regressionsmodellen abgeleitet. Im Mittelpunkt stehen die Paramter oberflächennahen Bodenfeuchte vegetationsfreier/-armer Flächen sowie die Biomasse landwirtschaftlicher Kulturen. Die Ergebnisse zeigen, daß mit ERS-1/-2 SAR-Daten eine Messung der Bodenfeuchte möglich ist, wenn Informationen zur Bodenrauhigkeit vorliegen. Hinsichtlich der biophysikalischen Parameter sind signifikante Zusammenhänge zwischen der Frisch- bzw. Trockenmasse des Vegetationsbestandes verschiedener Getreide und dem Radarsignal nachweisbar. Die Biomasse-Informationen können zur Korrektur von Wachstumsmodellen genutzt werden und dazu beitragen, die Genauigkeit von Ertragsschätzungen zu steigern.

Charakterisierung der Vinorin-Synthase aus Rauvolfia serpentina durch Reinigung, Expression, Mutation und Kristallisation

ABSTRACTDie vorliegende Arbeit befasste sich mit der Reinigung,heterologen Expression, Charakterisierung, molekularenAnalyse, Mutation und Kristallisation des EnzymsVinorin-Synthase. Das Enzym spielt eine wichtige Rolle inder Ajmalin-Biosynthese, da es in einerAcetyl-CoA-abhängigen Reaktion die Umwandlung desSarpagan-Alkaloids 16-epi-Vellosimin zu Vinorin unterBildung des Ajmalan-Grundgerüstes katalysiert. Nach der Reinigung der Vinorin-Synthase ausHybrid-Zellkulturen von Rauvolfia serpentina/Rhazya strictamit den fünf chromatographischen TrennmethodenAnionenaustauschchromatographie an SOURCE 30Q, HydrophobeInteraktionen Chromatographie an SOURCE 15PHE,Chromatographie an MacroPrep Ceramic Hydroxyapatit,Anionenaustauschchromatographie an Mono Q undGrößenausschlußchromatographie an Superdex 75 konnte dieVinorin-Synthase aus 2 kg Zellkulturgewebe 991fachangereichert werden.Das nach der Reinigung angefertigte SDS-Gel ermöglichte eineklare Zuordnung der Protein-Bande als Vinorin-Synthase.Der Verdau der Enzymbande mit der Endoproteinase LysC unddie darauffolgende Sequenzierung der Spaltpeptide führte zuvier Peptidsequenzen. Der Datenbankvergleich (SwissProt)zeigte keinerlei Homologien zu Sequenzen bekannterPflanzenenzyme. Mit degenerierten Primern, abgeleitet voneinem der erhaltenen Peptidfragmente und einer konserviertenRegion bekannter Acetyltransferasen gelang es, ein erstescDNA-Fragment der Vinorin-Synthase zu amplifizieren. Mit derMethode der RACE-PCR wurde die Nukleoidsequenzvervollständigt, was zu einem cDNA-Vollängenklon mit einerGröße von 1263 bp führte, der für ein Protein mit 421Aminosäuren (46 kDa) codiert.Das Vinorin-Synthase-Gen wurde in den pQE2-Expressionsvektorligiert, der für einen N-terminalen 6-fachen His-tagcodiert. Anschließend wurde sie erstmals erfolgreich in E.coli im mg-Maßstab exprimiert und bis zur Homogenitätgereinigt. Durch die erfolgreiche Überexpression konnte dieVinorin-Synthase eingehend charakterisiert werden. DerKM-Wert für das Substrat Gardneral wurde mit 20 µM, bzw.41.2 µM bestimmt und Vmax betrug 1 pkat, bzw. 1.71 pkat.Nach erfolgreicher Abspaltung des His-tags wurden diekinetischen Parameter erneut bestimmt (KM- Wert 7.5 µM, bzw.27.52 µM, Vmax 0.7 pkat, bzw. 1.21 pkat). Das Co-Substratzeigt einen KM- Wert von 60.5 µM (Vmax 0.6 pkat). DieVinorin-Synthase besitzt ein Temperatur-Optimum von 35 °Cund ein pH-Optimum bei 7.8.Homologievergleiche mit anderen Enzymen zeigten, dass dieVinorin-Synthase zu einer noch kleinen Familie von bisher 10Acetyltransferasen gehört. Alle Enzyme der Familie haben einHxxxD und ein DFGWG-Motiv zu 100 % konserviert. Basierendauf diesen Homologievergleichen und Inhibitorstudien wurden11 in dieser Proteinfamilie konservierte Aminosäuren gegenAlanin ausgetauscht, um so die Aminosäuren einer in derLiteratur postulierten katalytischen Triade(Ser/Cys-His-Asp) zu identifizieren.Die Mutation aller vorhandenen konservierten Serine undCysteine resultierte in keiner Mutante, die zumvollständigen Aktivitätsverlust des Enzyms führte. Nur dieMutationen H160A und D164A resultierten in einemvollständigen Aktivitätsverlust des Enzyms. Dieses Ergebniswiderlegt die Theorie einer katalytischen Triade und zeigte,dass die Aminosäuren H160A und D164A exklusiv an derkatalytischen Reaktion beteiligt sind.Zur Überprüfung dieser Ergebnisse und zur vollständigenAufklärung des Reaktionsmechanismus wurde dieVinorin-Synthase kristallisiert. Die bis jetzt erhaltenenKristalle (Kristallgröße in µm x: 150, y: 200, z: 200)gehören der Raumgruppe P212121 (orthorhombisch primitiv) anund beugen bis 3.3 Å. Da es bis jetzt keine Kristallstruktureines zur Vinorin-Synthase homologen Proteins gibt, konntedie Struktur noch nicht vollständig aufgeklärt werden. ZurLösung des Phasenproblems wird mit der Methode der multiplenanomalen Dispersion (MAD) jetzt versucht, die ersteKristallstruktur in dieser Enzymfamilie aufzuklären.

Phylogenomische Analysen bei Metazoen - Zur Stellung der Xenoturbellida und Syndermata

Im Rahmen der vorliegenden Dissertation wurde die phylogenetischen Stellungen der Xenoturbellida (Deuterostomia) und der Syndermata (Protostomia) mit phylogenomischen Techniken untersucht. Auf methodischer Ebene konnte gezeigt werden, dass ribosomale Proteine aufgrund ihres mittleren bis hohen Konservierungsgrades, ihrer Häufigkeit in kleineren EST-Projekten, damit verbunden ihrer Häufigkeit in Datenbanken und ihres phylogenetischen Informationsgehalts nützliche Werkzeuge für phylogenetische Fragestellungen sind. Es konnte durch phylogenetische Rekonstruktionen und Hypothesentests auf Basis eines 11.912 Aminosäuren langen Datensatzes gezeigt werden, dass die Xenoturbellida innerhalb der Deuterostomia eine Schwestergruppenbeziehung zu den Ambulacraria eingehen. Diese Arbeit zeigt im Vergleich aller bisher durchgeführten Arbeiten die beste statistische Unterstützung für diese Topologie. Weiterhin konnte untermauert werden, dass die Urochordata vermutlich anstelle der Cephalochordata die Schwestergruppe der Vertebrata sind. Der Vergleich der publizierten Xenoturbella EST-Datensätze mit dem eigenen Datensatz ließ den Rückschluß zu, dass ESTs offenbar klar weniger anfällig gegen Kontaminationen mit Erbmaterial (DNA+RNA) anderer Spezies sind als PCR-Amplifikate genomischer oder mitochondrialer Gene. Allerdings bestimmt anscheinend der physiologische Zustand der Tiere die Repräsentation von Transkriptklassen wie Stressproteine und mitochondriale Transkripte. Die bakteriellen Transkripte in einem der EST-Datensätze stammen vermutlich von Chlamydien, die möglicherweise symbiontisch in Xenoturbella bocki leben. Im Bereich der Protostomia wurden drei EST-Projekte für Vertreter der Syndermata durchgeführt. Basierend auf drei verschiedenen Proteinalignment-Datensätzen von ca. 11.000 Aminosäuren Länge konnte gezeigt werden, dass die Syndermata innerhalb der Spiralia einzugruppieren sind und dass sie mit den Gnathostomulida das monophyletische Supertaxon Gnathifera bilden. Die genaue phylogenetische Position der Syndermata innerhalb der Spiralia konnte hingegen noch nicht eindeutig geklärt werden, ebenso wie kein kongruenter Beweis für die Existenz des Supertaxons Platyzoa gefunden werden konnte. Im Rahmen der Untersuchung der internen Phylogenie der Syndermata konnten drei der fünf konkurrierenden Hypothesen aufgrund der Paraphylie der Eurotatoria ausgeschlossen werden. Da keine Daten der Seisonidea in den Analysen implementiert waren, bleibt die Frage der internen Phylogenie der Syndermata letztlich offen. Klar ist jedoch, dass die Eurotatoria nicht wie bislang angenommen monophyletisch sind, da die räderorgantragenden Bdelloidea keinesfalls den morphologisch diesbezüglich ähnlichen Monogononta ähnlich sind, sondern den räderorganlosen Acanthocephala näher stehen. Die Abbildung der molekularen Phylogenie auf die morphologischen Verhältnisse zeigt, dass das Räderorgan (partiell oder komplett) offenbar kurz nach der Aufspaltung der Syndermata in Monogononta und Acanthocephala + Bdelloidea in der Acanthocephala + Bdelloidea-Linie reduziert wurde. Die Entstehung des einziehbaren hinteren Körperteils (Rostrum bei Bdelloidea bzw. Proboscis bei Acanthocephala) in der Acanthocephala + Bdelloidea-Linie könnte das Schlüsselereignis zur Entstehung des Endoparasitismus der Acanthocephala gewesen sein.