A parallel solution to linear systems

Streaming SIMD Extensions (SSE) is a unique feature embedded in the Pentium III and IV classes of microprocessors. By fully exploiting SSE, parallel algorithms can be implemented on a standard personal computer and a theoretical speedup of four can be achieved. In this paper, we demonstrate the implementation of a parallel LU matrix decomposition algorithm for solving linear systems with SSE and discuss advantages and disadvantages of this approach based on our experimental study.

PartSS : An efficient partition-based filtering for edit distance constraints

This paper introduces PartSS, a new partition-based fil- tering for tasks performing string comparisons under edit distance constraints. PartSS offers improvements over the state-of-the-art method NGPP with the implementation of a new partitioning scheme and also improves filtering abil- ities by exploiting theoretical results on shifting and scaling ranges, thus accelerating the rate of calculating edit distance between strings. PartSS filtering has been implemented within two major tasks of data integration: similarity join and approximate membership extraction under edit distance constraints. The evaluation on an extensive range of real-world datasets demonstrates major gain in efficiency over NGPP and QGrams approaches.

Slide attacks on the Sfinks stream cipher

Sfinks is a shift register based stream cipher designed for hardware implementation and submitted to the eSTREAM project. In this paper, we analyse the initialisation process of Sfinks. We demonstrate a slid property of the loaded state of the Sfinks cipher, where multiple key-IV pairs may produce phase shifted keystream sequences. The state update functions of both the initialisation process and keystream generation and also the pattern of the padding affect generation of the slid pairs.

A two-stage approach for generating topic models

Topic modeling has been widely utilized in the fields of information retrieval, text mining, text classification etc. Most existing statistical topic modeling methods such as LDA and pLSA generate a term based representation to represent a topic by selecting single words from multinomial word distribution over this topic. There are two main shortcomings: firstly, popular or common words occur very often across different topics that bring ambiguity to understand topics; secondly, single words lack coherent semantic meaning to accurately represent topics. In order to overcome these problems, in this paper, we propose a two-stage model that combines text mining and pattern mining with statistical modeling to generate more discriminative and semantic rich topic representations. Experiments show that the optimized topic representations generated by the proposed methods outperform the typical statistical topic modeling method LDA in terms of accuracy and certainty.

Count-min sketches for estimating password frequency within Hamming distance two

The count-min sketch is a useful data structure for recording and estimating the frequency of string occurrences, such as passwords, in sub-linear space with high accuracy. However, it cannot be used to draw conclusions on groups of strings that are similar, for example close in Hamming distance. This paper introduces a variant of the count-min sketch which allows for estimating counts within a specified Hamming distance of the queried string. This variant can be used to prevent users from choosing popular passwords, like the original sketch, but it also allows for a more efficient method of analysing password statistics.

Analysis of cardiac and epileptic signals using higher order spectra

The theory of nonlinear dyamic systems provides some new methods to handle complex systems. Chaos theory offers new concepts, algorithms and methods for processing, enhancing and analyzing the measured signals. In recent years, researchers are applying the concepts from this theory to bio-signal analysis. In this work, the complex dynamics of the bio-signals such as electrocardiogram (ECG) and electroencephalogram (EEG) are analyzed using the tools of nonlinear systems theory. In the modern industrialized countries every year several hundred thousands of people die due to sudden cardiac death. The Electrocardiogram (ECG) is an important biosignal representing the sum total of millions of cardiac cell depolarization potentials. It contains important insight into the state of health and nature of the disease afflicting the heart. Heart rate variability (HRV) refers to the regulation of the sinoatrial node, the natural pacemaker of the heart by the sympathetic and parasympathetic branches of the autonomic nervous system. Heart rate variability analysis is an important tool to observe the heart's ability to respond to normal regulatory impulses that affect its rhythm. A computerbased intelligent system for analysis of cardiac states is very useful in diagnostics and disease management. Like many bio-signals, HRV signals are non-linear in nature. Higher order spectral analysis (HOS) is known to be a good tool for the analysis of non-linear systems and provides good noise immunity. In this work, we studied the HOS of the HRV signals of normal heartbeat and four classes of arrhythmia. This thesis presents some general characteristics for each of these classes of HRV signals in the bispectrum and bicoherence plots. Several features were extracted from the HOS and subjected an Analysis of Variance (ANOVA) test. The results are very promising for cardiac arrhythmia classification with a number of features yielding a p-value < 0.02 in the ANOVA test. An automated intelligent system for the identification of cardiac health is very useful in healthcare technology. In this work, seven features were extracted from the heart rate signals using HOS and fed to a support vector machine (SVM) for classification. The performance evaluation protocol in this thesis uses 330 subjects consisting of five different kinds of cardiac disease conditions. The classifier achieved a sensitivity of 90% and a specificity of 89%. This system is ready to run on larger data sets. In EEG analysis, the search for hidden information for identification of seizures has a long history. Epilepsy is a pathological condition characterized by spontaneous and unforeseeable occurrence of seizures, during which the perception or behavior of patients is disturbed. An automatic early detection of the seizure onsets would help the patients and observers to take appropriate precautions. Various methods have been proposed to predict the onset of seizures based on EEG recordings. The use of nonlinear features motivated by the higher order spectra (HOS) has been reported to be a promising approach to differentiate between normal, background (pre-ictal) and epileptic EEG signals. In this work, these features are used to train both a Gaussian mixture model (GMM) classifier and a Support Vector Machine (SVM) classifier. Results show that the classifiers were able to achieve 93.11% and 92.67% classification accuracy, respectively, with selected HOS based features. About 2 hours of EEG recordings from 10 patients were used in this study. This thesis introduces unique bispectrum and bicoherence plots for various cardiac conditions and for normal, background and epileptic EEG signals. These plots reveal distinct patterns. The patterns are useful for visual interpretation by those without a deep understanding of spectral analysis such as medical practitioners. It includes original contributions in extracting features from HRV and EEG signals using HOS and entropy, in analyzing the statistical properties of such features on real data and in automated classification using these features with GMM and SVM classifiers.

Conservation Properties of the Trapezoidal Rule in Linear Time Domain Analysis of Acoustics and Structures

The trapezoidal rule, which is a special case of the Newmark family of algorithms, is one of the most widely used methods for transient hyperbolic problems. In this work, we show that this rule conserves linear and angular momenta and energy in the case of undamped linear elastodynamics problems, and an ``energy-like measure'' in the case of undamped acoustic problems. These conservation properties, thus, provide a rational basis for using this algorithm. In linear elastodynamics problems, variants of the trapezoidal rule that incorporate ``high-frequency'' dissipation are often used, since the higher frequencies, which are not approximated properly by the standard displacement-based approach, often result in unphysical behavior. Instead of modifying the trapezoidal algorithm, we propose using a hybrid finite element framework for constructing the stiffness matrix. Hybrid finite elements, which are based on a two-field variational formulation involving displacement and stresses, are known to approximate the eigenvalues much more accurately than the standard displacement-based approach, thereby either bypassing or reducing the need for high-frequency dissipation. We show this by means of several examples, where we compare the numerical solutions obtained using the displacement-based and hybrid approaches against analytical solutions.

Analysis of Differential and Matching Methods for Optical Flow

Several algorithms for optical flow are studied theoretically and experimentally. Differential and matching methods are examined; these two methods have differing domains of application- differential methods are best when displacements in the image are small (<2 pixels) while matching methods work well for moderate displacements but do not handle sub-pixel motions. Both types of optical flow algorithm can use either local or global constraints, such as spatial smoothness. Local matching and differential techniques and global differential techniques will be examined. Most algorithms for optical flow utilize weak assumptions on the local variation of the flow and on the variation of image brightness. Strengthening these assumptions improves the flow computation. The computational consequence of this is a need for larger spatial and temporal support. Global differential approaches can be extended to local (patchwise) differential methods and local differential methods using higher derivatives. Using larger support is valid when constraint on the local shape of the flow are satisfied. We show that a simple constraint on the local shape of the optical flow, that there is slow spatial variation in the image plane, is often satisfied. We show how local differential methods imply the constraints for related methods using higher derivatives. Experiments show the behavior of these optical flow methods on velocity fields which so not obey the assumptions. Implementation of these methods highlights the importance of numerical differentiation. Numerical approximation of derivatives require care, in two respects: first, it is important that the temporal and spatial derivatives be matched, because of the significant scale differences in space and time, and, second, the derivative estimates improve with larger support.

Performance Analysis of a Low Complexity Detector for MCIK-OFDM over TWDP Fading

This letter analyzes the performance of a low complexity detection scheme for a multi-carrier index keying (MCIK) with orthogonal frequency division multiplexing (OFDM) system over two-wave with diffused power (TWDP) fading channels. A closed-form expression for the average pairwise error probability (PEP) over TWDP fading channels is derived. This expression is used to analyze the performance of MCIK-OFDM in moderate, severe and extreme fading conditions. The presented results provide an insight on the performance of MCIK-OFDM for wireless communication systems that operate in enclosed metallic structures such as in-vehicular device-to-device (D2D) wireless networks.

Structural analysis of glycans and development of microarrays from Helcobacter pylori cell surface glycome

Helicobacter pylori is a bacterial pathogen that affects more than half of the world’s population with gastro-intestinal diseases and is associated with gastric cancer. The cell surface of H. pylori is decorated with lipopolysaccharides (LPSs) composed of three distinct regions: a variable polysaccharide moiety (O-chain), a structurally conserved core oligosaccharide, and a lipid A region that anchors the LPS to the cell membrane. The O-chain of H. pylori LPS, exhibits unique oligosaccharide structures, such as Lewis (Le) antigens, similar to those present in the gastric mucosa and are involved in interactions with the host. Glucan, heptoglycan, and riban domains are present in the outer core region of some H. pylori LPSs. Amylose-like glycans and mannans are also constituents of some H. pylori strains, possibly co-expressed with LPSs. The complexity of H. pylori LPSs has hampered the establishment of accurate structure-function relationships in interactions with the host, and the design of carbohydrate-based therapeutics, such as vaccines. Carbohydrate microarrays are recent powerful and sensitive tools for studying carbohydrate antigens and, since their emergence, are providing insights into the function of carbohydrates and their involvement in pathogen-host interactions. The major goals of this thesis were the structural analysis of LPSs from H. pylori strains isolated from gastric biopsies of symptomatic Portuguese patients and the construction of a novel pathogen carbohydrate microarray of these LPSs (H. pylori LPS microarray) for interaction studies with proteins. LPSs were extracted from the cell surface of five H. pylori clinical isolates and one NCTC strain (26695) by phenol/water method, fractionated by size exclusion chromatography and analysed by gas chromatography coupled to mass spectrometry. The oligosaccharides released after mild acid treatment of the LPS were analysed by electrospray mass spectrometry. In addition to the conserved core oligosaccharide moieties, structural analyses revealed the presence of type-2 Lex and Ley antigens and N-acetyllactosamine (LacNAc) sequences, typically found in H. pylori strains. Also, the presence of O-6 linked glucose residues, particularly in LPSs from strains 2191 and NCTC 26695, pointed out to the expression of a 6-glucan. Other structural domains, namely ribans, composed of O-2 linked ribofuranose residues were observed in the LPS of most of H. pylori clinical isolates. For the LPS from strain 14382, large amounts of O-3 linked galactose units, pointing to the occurrence of a galactan, a domain recently identified in the LPS of another H. pylori strain. A particular feature to the LPSs from strains 2191 and CI-117 was the detection of large amounts of O-4 linked N-acetylglucosamine (GlcNAc) residues, suggesting the presence of chitin-like glycans, which to our knowledge have not been described for H. pylori strains. For the construction of the H. pylori LPS microarray, the structurally analysed LPSs, as well as LPS-derived oligosaccharide fractions, prepared as neoglycolipid (NGL) probes were noncovalently immobilized onto nitrocellulosecoated glass slides. These were printed together with NGLs of selected sequence defined oligosaccharides, bacterial LPSs and polysaccharides. The H. pylori LPS microarray was probed for recognition with carbohydratebinding proteins (CBPs) of known specificity. These included Le and blood group-related monoclonal antibodies (mAbs), plant lectins, a carbohydratebinding module (CBM) and the mammalian immune receptors DC-SIGN and Dectin-1. The analysis of these CBPs provided new information that complemented the structural analyses and was valuable in the quality control of the constructed microarray. Microarray analysis revealed the occurrence of type-2 Lex and Ley, but not type-1 Lea or Leb antigens, supporting the results obtained in the structural analysis. Furthermore, the H. pylori LPSs were recognised by DC-SIGN, a mammalian lectin known to interact with this bacterium through fucosylated Le epitopes expressed in its LPSs. The -fucose-specific lectin UEA-I, showed restricted binding to probes containing type-2 blood group H sequence and to the LPSs from strains CI-117 and 14382. The presence of H-type-2, as well Htype- 1 in the LPSs from these strains, was confirmed using specific mAbs. Although H-type-1 determinant has been reported for H. pylori LPSs, this is the first report of the presence of H-type-2 determinant. Microarray analysis also revealed that plant lectins known to bind 4-linked GlcNAc chitin oligosaccharide sequences bound H. pylori LPSs. STL, which exhibited restricted and strong binding to 4GlcNAc tri- and pentasaccharides, differentially recognised the LPS from the strain CI-117. The chitin sequences recognised in the LPS could be internal, as no binding was detected to this LPS with WGA, known to be specific for nonreducing terminal of 4GlcNAc sequence. Analyses of the H. pylori LPSs by SDS-PAGE and Western blot with STL provided further evidence for the presence of these novel domains in the O-chain region of this LPS. H. pylori LPS microarray was also applied to analysis of two human sera. The first was from a case infected with H. pylori (H. pylori+ CI-5) and the second was from a non-infected control.The analysis revealed a higher IgG-reactivity towards H. pylori LPSs in the H. pylori+ serum, than the control serum. A specific IgG response was observed to the LPS isolated from the CI-5 strain, which caused the infection. The present thesis has contributed to extension of current knowledge on chemical structures of LPS from H. pylori clinical isolates. Furthermore, the H. pylori LPS microarray constructed enabled the study of interactions with host proteins and showed promise as a tool in serological studies of H. pyloriinfected individuals. Thus, it is anticipated that the use of these complementary approaches may contribute to a better understanding of the molecular complexity of the LPSs and their role in pathogenesis.

From design-for-test to design-for-debug-and-test: analysis of requirements and limitations for 1149.1

The increasing complexity of VLSI circuits and the reduced accessibility of modern packaging and mounting technologies restrict the usefulness of conventional in-circuit debugging tools, such as in-circuit emulators for microprocessors and microcontrollers. However, this same trend enables the development of more complex products, which in turn require more powerful debugging tools. These conflicting demands could be met if the standard scan test infrastructures now common in most complex components were able to match the debugging requirements of design verification and prototype validation. This paper analyses the main debug requirements in the design of microprocessor-based applications and the feasibility of their implementation using the mandatory, optional and additional operating modes of the standard IEEE 1149.1 test infrastructure.

A Foucauldian Analysis of Power and Representation in an Attempt to Run a Photovoice Project with Youth

This project evolved out of a search for ways to conduct research on “others” in a way that does not exploit, stigmatize or misrepresent their experience. This thesis is an ethnographic study in leisure research and youth work and an experiment in running a photovoice project. Photovoice is a participatory visual method that embodies the emancipatory ideal of empowering others through self-representation. The literature on photovoice lacks a comprehensive discussion on the complexity of power and representation. Postmodern theorists have proposed that participatory methods are not benign and that initiatives are acts of power in themselves that produce effects (Cook & Kothari, 2001). A Foucauldian analysis of power is used to deconstruct the researcher’s practice and reflect on why and how youth are “engaged”. This project seeks to embrace the principle of working “with” others, but also work from a postmodern perspective that acknowledges power and representation as ongoing problems.

Proteomic analysis of redox- and ErbB2-dependent changes in mammary luminal epithelial cells using cysteine- and lysine-labelling two-dimensional difference gel electrophoresis

Differential protein expression analysis based on modification of selected amino acids with labelling reagents has become the major method of choice for quantitative proteomics. One such methodology, two-dimensional difference gel electrophoresis (2-D DIGE), uses a matched set of fluorescent N-hydroxysuccinimidyl (NHS) ester cyanine dyes to label lysine residues in different samples which can be run simultaneously on the same gels. Here we report the use of iodoacetylated cyanine (ICy) dyes (for labelling of cysteine thiols, for 2-D DIGE-based redox proteomics. Characterisation of ICy dye labelling in relation to its stoichiometry, sensitivity and specificity is described, as well as comparison of ICy dye with NHS-Cy dye labelling and several protein staining methods. We have optimised conditions for labelling of nonreduced, denatured samples and report increased sensitivity for a subset of thiol-containing proteins, allowing accurate monitoring of redox-dependent thiol modifications and expression changes. Cysteine labelling was then combined with lysine labelling in a multiplex 2-D DIGE proteomic study of redox-dependent and ErbB2-dependent changes in epithelial cells exposed to oxidative stress. This study identifies differentially modified proteins involved in cellular redox regulation, protein folding, proliferative suppression, glycolysis and cytoskeletal organisation, revealing the complexity of the response to oxidative stress and the impact that overexpression of ErbB2 has on this response.

Proteomic analysis of redox- and ErbB2-dependent changes in mammary luminal epithelial cells using cysteine- and lysine-labelling two-dimensional difference gel electrophoresis

Differential protein expression analysis based on modification of selected amino acids with labelling reagents has become the major method of choice for quantitative proteomics. One such methodology, two-dimensional difference gel electrophoresis (2-D DIGE), uses a matched set of fluorescent N-hydroxysuccinimidyl (NHS) ester cyanine dyes to label lysine residues in different samples which can be run simultaneously on the same gels. Here we report the use of iodoacetylated cyanine (ICy) dyes (for labelling of cysteine thiols, for 2-D DIGE-based redox proteomics. Characterisation of ICy dye labelling in relation to its stoichiometry, sensitivity and specificity is described, as well as comparison of ICy dye with NHS-Cy dye labelling and several protein staining methods. We have optimised conditions for labelling of nonreduced, denatured samples and report increased sensitivity for a subset of thiol-containing proteins, allowing accurate monitoring of redox-dependent thiol modifications and expression changes, Cysteine labelling was then combined with lysine labelling in a multiplex 2-D DIGE proteomic study of redox-dependent and ErbB2-dependent changes in epithelial cells exposed to oxidative stress. This study identifies differentially modified proteins involved in cellular redox regulation, protein folding, proliferative suppression, glycolysis and cytoskeletal organisation, revealing the complexity of the response to oxidative stress and the impact that overexpression of ErbB2 has on this response.

Comparison of pollinators and natural enemies: a meta-analysis of landscape and local effects on abundance and richness in crops

To manage agroecosystems for multiple ecosystem services, we need to know whether the management of one service has positive, negative, or no effects on other services. We do not yet have data on the interactions between pollination and pest-control services. However, we do have data on the distributions of pollinators and natural enemies in agroecosystems. Therefore, we compared these two groups of ecosystem service providers, to see if the management of farms and agricultural landscapes might have similar effects on the abundance and richness of both. In a meta-analysis, we compared 46 studies that sampled bees, predatory beetles, parasitic wasps, and spiders in fields, orchards, or vineyards of food crops. These studies used the proximity or proportion of non-crop or natural habitats in the landscapes surrounding these crops (a measure of landscape complexity), or the proximity or diversity of non-crop plants in the margins of these crops (a measure of local complexity), to explain the abundance or richness of these beneficial arthropods. Compositional complexity at both landscape and local scales had positive effects on both pollinators and natural enemies, but different effects on different taxa. Effects on bees and spiders were significantly positive, but effects on parasitoids and predatory beetles (mostly Carabidae and Staphylinidae) were inconclusive. Landscape complexity had significantly stronger effects on bees than it did on predatory beetles and significantly stronger effects in non-woody rather than in woody crops. Effects on richness were significantly stronger than effects on abundance, but possibly only for spiders. This abundance-richness difference might be caused by differences between generalists and specialists, or between arthropods that depend on non-crop habitats (ecotone species and dispersers) and those that do not (cultural species). We call this the ‘specialist-generalist’ or ‘cultural difference’ mechanism. If complexity has stronger effects on richness than abundance, it might have stronger effects on the stability than the magnitude of these arthropod-mediated ecosystem services. We conclude that some pollinators and natural enemies seem to have compatible responses to complexity, and it might be possible to manage agroecosystems for the benefit of both. However, too few studies have compared the two, and so we cannot yet conclude that there are no negative interactions between pollinators and natural enemies, and no trade-offs between pollination and pest-control services. Therefore, we suggest a framework for future research to bridge these gaps in our knowledge.