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.

Design, realization and characterization of automated millifluidic bioreactors for investigating the molecular evolution of lytic or lysogenic vector phages infecting engineered host e. Coli

In questa tesi viene presentato un bioreattore in grado di mantenere nel tempo condizioni biologiche tali che consentano di massimizzare i cicli di evoluzione molecolare di vettori di clonazione fagici: litico (T7) o lisogeno (M13). Verranno quindi introdtti concetti legati alla Teoria della Quasispecie e alla relazione tra errori di autoreplicazione e pressioni selettive naturali o artificiali su popolazioni di virus: il modello naturale del sistema evolutivo. Tuttavia, mantenere delle popolazioni di virus significa formire loro un substrato dove replicare. Per fare ciò, altri gruppi di ricerca hanno giá sviluppato complessi e costosi prototipi di macchinari per la crescita continua di popolazioni batteriche: i compartimenti dei sistemi evolutivi. Il bioreattore, oggetto di questo lavoro, fa parte del progetto europeo Evoprog: general purpose programmable machine evolution on a chip (Jaramillo’s Lab, University of Warwick) che, utilizzando tecnologie fagiche e regolazioni sintetiche esistenti, sará in grado di produrre funzionalità biocomputazionali di due ordini di grandezza più veloci rispetto alle tecniche convenzionali, riducendo allo stesso tempo i costi complessivi. Il primo prototipo consiste in uno o piú fermentatori, dove viene fatta crescere la cultura batterica in condizioni ottimizzate di coltivazione continua, e in un cellstat, un volume separato, dove avviene solo la replicazione dei virus. Entrambi i volumi sono di pochi millilitri e appropriatamente interconnessi per consentire una sorta di screening continuo delle biomolecole prodotte all’uscita. Nella parte finale verranno presentati i risultati degli esperimenti preliminari, a dimostrazione dell’affidabilità del prototipo costruito e dei protocolli seguiti per la sterilizzazione e l’assemblaggio del bioreattore. Gli esperimenti effettuati dimostrano il successo di due coltivazioni virali continue e una ricombinazione in vivo di batteriofagi litici o lisogeni ingegnerizzati. La tesi si conclude valutando i futuri sviluppi e i limiti del sistema, tenendo in considerazione, in particolare, alcune applicazioni rivolte agli studi di una terapia batteriofagica.

A method for automated generation of radiotherapy treatment plans for lung cancer

La radioterapia è una tecnica molto impiegata per la cura del cancro. Attualmente la somministrazione avviene principalmente attraverso la intensity modulated radiotherapy (IMRT, sovrapposizione di campi ad intensità modulata), un cui sviluppo recente è la volumetric modulated arc therapy (VMAT, irradiazione continua lungo un arco ininterrotto). La generazione di piani richiede esperienza ed abilità: un dosimetrista seleziona cost functions ed obiettivi ed un TPS ottimizza la disposizione dei segmenti ad intensità modulata. Se il medico giudica il risultato non soddisfacente, il processo riparte da capo (trial-and-error). Una alternativa è la generazione automatica di piani. Erasmus-iCycle, software prodotto presso ErasmusMC (Rotterdam, The Netherlands), è un algoritmo di ottimizzazione multicriteriale di piani radioterapici per ottimizzazione di intensità basato su una wish list. L'output consiste di piani Pareto-ottimali ad intensità modulata. La generazione automatica garantisce maggiore coerenza e qualità più elevata con tempi di lavoro ridotti. Nello studio, una procedura di generazione automatica di piani con modalità VMAT è stata sviluppata e valutata per carcinoma polmonare. Una wish list è stata generata attraverso una procedura iterativa su un gruppo ristretto di pazienti con la collaborazione di fisici medici ed oncologi e poi validata su un gruppo più ampio di pazienti. Nella grande maggioranza dei casi, i piani automatici sono stati giudicati dagli oncologi migliori rispetto ai rispettivi piani IMRT clinici generati manualmente. Solo in pochi casi una rapida calibrazione manuale specifica per il paziente si è resa necessaria per soddisfare tutti i requisiti clinici. Per un sottogruppo di pazienti si è mostrato che la qualità dei piani VMAT automatici era equivalente o superiore rispetto ai piani VMAT generati manualmente da un dosimetrista esperto. Complessivamente, si è dimostrata la possibilità di generare piani radioterapici VMAT ad alta qualità automaticamente, con interazione umana minima. L'introduzione clinica della procedura automatica presso ErasmusMC è iniziata (ottobre 2015).

Atlas-Based Segmentation of Brain Tumor Images Using a Markov Random Field-Based Tumor Growth Model and Non-Rigid Registration

We propose a new and clinically oriented approach to perform atlas-based segmentation of brain tumor images. A mesh-free method is used to model tumor-induced soft tissue deformations in a healthy brain atlas image with subsequent registration of the modified atlas to a pathologic patient image. The atlas is seeded with a tumor position prior and tumor growth simulating the tumor mass effect is performed with the aim of improving the registration accuracy in case of patients with space-occupying lesions. We perform tests on 2D axial slices of five different patient data sets and show that the approach gives good results for the segmentation of white matter, grey matter, cerebrospinal fluid and the tumor.

Automated Intervertebral Disc Detection from Low Resolution, Sparse MRI Images for the Planning of Scan Geometries

Robust and accurate identification of intervertebral discs from low resolution, sparse MRI scans is essential for the automated scan planning of the MRI spine scan. This paper presents a graphical model based solution for the detection of both the positions and orientations of intervertebral discs from low resolution, sparse MRI scans. Compared with the existing graphical model based methods, the proposed method does not need a training process using training data and it also has the capability to automatically determine the number of vertebrae visible in the image. Experiments on 25 low resolution, sparse spine MRI data sets verified its performance.

Automated detection of fiducial screws from CT/DVT volume data for image-guided ENT surgery

This paper presents an automated solution for precise detection of fiducial screws from three-dimensional (3D) Computerized Tomography (CT)/Digital Volume Tomography (DVT) data for image-guided ENT surgery. Unlike previously published solutions, we regard the detection of the fiducial screws from the CT/DVT volume data as a pose estimation problem. We thus developed a model-based solution. Starting from a user-supplied initialization, our solution detects the fiducial screws by iteratively matching a computer aided design (CAD) model of the fiducial screw to features extracted from the CT/DVT data. We validated our solution on one conventional CT dataset and on five DVT volume datasets, resulting in a total detection of 24 fiducial screws. Our experimental results indicate that the proposed solution achieves much higher reproducibility and precision than the manual detection. Further comparison shows that the proposed solution produces better results on the DVT dataset than on the conventional CT dataset.

Fully Automatic Segmentation of Brain Tumor Images using Support Vector Machine Classiffication in Combination with Hierarchical Conditional Random Field Regularization

Delineating brain tumor boundaries from magnetic resonance images is an essential task for the analysis of brain cancer. We propose a fully automatic method for brain tissue segmentation, which combines Support Vector Machine classification using multispectral intensities and textures with subsequent hierarchical regularization based on Conditional Random Fields. The CRF regularization introduces spatial constraints to the powerful SVM classification, which assumes voxels to be independent from their neighbors. The approach first separates healthy and tumor tissue before both regions are subclassified into cerebrospinal fluid, white matter, gray matter and necrotic, active, edema region respectively in a novel hierarchical way. The hierarchical approach adds robustness and speed by allowing to apply different levels of regularization at different stages. The method is fast and tailored to standard clinical acquisition protocols. It was assessed on 10 multispectral patient datasets with results outperforming previous methods in terms of segmentation detail and computation times.

Segmentation of brain tumor images based on atlas-registration combined with a Markov-Random-Field lesion growth model

We present an automatic method to segment brain tissues from volumetric MRI brain tumor images. The method is based on non-rigid registration of an average atlas in combination with a biomechanically justified tumor growth model to simulate soft-tissue deformations caused by the tumor mass-effect. The tumor growth model, which is formulated as a mesh-free Markov Random Field energy minimization problem, ensures correspondence between the atlas and the patient image, prior to the registration step. The method is non-parametric, simple and fast compared to other approaches while maintaining similar accuracy. It has been evaluated qualitatively and quantitatively with promising results on eight datasets comprising simulated images and real patient data.

Automated detection of the osseous acetabular rim using three-dimensional models of the pelvis

An automated algorithm for detection of the acetabular rim was developed. Accuracy of the algorithm was validated in a sawbone study and compared against manually conducted digitization attempts, which were established as the ground truth. The latter proved to be reliable and reproducible, demonstrated by almost perfect intra- and interobserver reliability. Validation of the automated algorithm showed no significant difference compared to the manually acquired data in terms of detected version and inclination. Automated detection of the acetabular rim contour and the spatial orientation of the acetabular opening plane can be accurately achieved with this algorithm.