Subsequence frequency measurement and its impact on knowledge discovery in single sequences

Subsequence frequency measurement is a basic and essential problem in knowledge discovery in single sequences. Frequency based knowledge discovery in single sequences tends to be unreliable since different resulting sets may be obtained from a same sequence when different frequency metrics are adopted. In this chapter, we investigate subsequence frequency measurement and its impact on the reliability of knowledge discovery in single sequences. We analyse seven previous frequency metrics, identify their inherent inaccuracies, and explore their impacts on two kinds of knowledge discovered from single sequences, frequent episodes and episode rules. We further give three suggestions for frequency metrics and introduce a new frequency metric in order to improve the reliability. Empirical evaluation reveals the inaccuracies and verifies our findings.

Implementing recovery in low-resource stationary wireless sensor networks

Implementation of certain types of protocols on wireless sensor networks (WSNs) can be difficult due to the architecture of the motes. Identification of these issues and recommendations for workarounds can be very useful for the WSN research community testing hardware. In recent work, the authors developed and implemented clustering, reprogramming and authentication protocols involved in recovering WSNs with low resources. In attempting to integrate these protocols, several issues arose in the implementation phase connected to pre-set configurations of the motes used. In this paper, we describe the issues arising in integrating our protocols using Zigbee with IEEE 802.15.4 and the reprogramming module Deluge, and compare our challenges and solutions with those faced by other researchers in this area. Finally, we provide recommendations for consideration by researchers who may in future consider integrating several protocols on these platforms.

Highly efficient serial episode discovery in streams and complex sequences

This research proposed a series of methodologies and algorithms for highly efficient serial episode discovery in streams and complex sequences, and applied the developed techniques to quantitative analysis of the effects of price promotions. This research has outputted nine ERA ranking AlB papers published in international journals and conferences.

Qualitative estimation of camera motion parameters from video sequences

We propose a simple technique for extracting camera motion parameters from a sequence of images. The method can estimate qualitatively camera pan, tilt, zoom, roll, and horizontal and vertical tracking. Unlike most other comparable techniques, the present method can distinguish pan from horizontal tracking, and tilt from vertical tracking. The technique can be applied to the automated indexing of video and film sequences.

Two-dimensional string notation for representing video sequences

Most current work on video indexing concentrates on queries which operate over high level semantic information which must be entirely composed and entered manually. We propose an indexing system which is based on spatial information about key objects in a scene. These key objects may be detected automatically, with manual supervision, and tracked through a sequence using one of a number of recently developed techniques. This representation is highly compact and allows rapid resolution of queries specified by iconic example. A number of systems have been produced which use 2D string notations to index digital image libraries. Just as 2D strings provide a compact and tractable indexing notation for digital pictures, a sequence of 2D strings might provide an index for a video or image sequence. To improve further upon this we reduce the representation to the 2D string pair representing the initial frame, and a sequence of edits to these strings. This takes advantage of the continuity between frames to further reduce the size of the notation. By representing video sequences using string edits, a notation has been developed which is compact, and allows querying on the spatial relationships of objects to be performed without rebuilding the majority of the scene. Calculating ranks of objects directly from the edit sequence allows matching with minimal calculation, thus greatly reducing search time. This paper presents the edit sequence notation and algorithms for evaluating queries over image sequences. A number of optimizations which represent a considerably saving in search time is demonstrated in the paper.

Generating comprehensible summaries of rushes sequences based on robust feature matching

This paper describes our first attempt at tackling a pilot task in Trecvid: video summarization of rushes data [3]. Our method is based on the tight clustering produced via SIFT matching. In this first attempt, we try to examine how our approach performs without complex implementation in terms of concept detection and excerpt assembly (i.e, no picture-in-picture, split screen and special transitions). Although we do not perform very well in terms of concept inclusion, we rank very well in terms of the summary being easy to understand and relevancy of included segments.

Finding the optimal temporal partitioning of video sequences

The existing techniques for shot partitioning either process each shot boundary independently or proceed sequentially. The sequential process assumes the last shot boundary is correctly detected and utilizes the shot length distribution to adapt the threshold for detecting the next boundary. These techniques are only locally optimal and suffer from the strong assumption about the correct detection of the last boundary. Addressing these fundamental issues, in this paper, we aim to find the global optimal shot partitioning by utilizing Bayesian principles to model the probability of a particular video partition being the shot partition. A computationally efficient algorithm based on Dynamic Programming is then formulated. The experimental results on a large movie set show that our algorithm performs consistently better than the best adaptive-thresholding technique commonly used for the task.

Explicit state duration HMM for abnormality detection in sequences of human activity

The importance of explicit duration modelling for classification of sequences of human activity and the reliable and timely detection of duration abnormality was highlighted. The normal classes of behavior were designed to highlight the importance of modelling duration given the limitations of the tracking system. It was found that HMM was the weakest model for classification of the unseen normal sequences with 81% accuracy. Long term abnormality was investigated by artificially varying the duration of primary activity in a randomly selected test sequence. The incorporation of duration in models of human behavior is an important consideration for systems seeking to provide cognitive support and to detect deviation in the behavorial patterns.

Towards detecting patterns of human behaviour from image sequences

This paper details research that will explore the analysis of human behaviour via video surveillance. Digital computer images will be obtained from video footage of a real world scene, and positions of people in the scene will be identified and tracked through each frame in the sequence.

The noted positions will build into a pattern of motion that can be examined and classified. It is proposed that specific events, such as panic or fight situations, will have unique, and therefore identifying, characteristics that will enable automatic detection of such events.

It is envisaged that active cameras will be used when a situation of interest occurs, to enable more information to be extracted from the scene (e.g., panning to follow action, or zooming to enhance detail.)

Mining condensed sets of frequent episodes with more accurate frequencies from complex sequences

Many previous approaches to frequent episode discovery only accept simple sequences. Although a recent approach has been able to nd frequent episodes from complex sequences, the discovered sets are neither condensed nor accurate. This paper investigates the discovery of condensed sets of frequent episodes from complex sequences. We adopt a novel anti-monotonic frequency measure based on non-redundant occurrences, and dene a condensed set, nDaCF (the set of non-derivable approximately closed frequent episodes) within a given maximal error bound of support. We then introduce a series of effective pruning strategies, and develop a method, nDaCF-Miner, for discovering nDaCF sets. Experimental results show that, when the error bound is somewhat high, the discovered nDaCF sets are two orders of magnitude smaller than complete sets, and nDaCF-miner is more efficient than previous mining approaches. In addition, the nDaCF sets are more accurate than the sets found by previous approaches.

Effects of alterations of primer-binding site sequences on human immunodeficiency virus type 1 replication

The human immunodeficiency virus type 1 genomic RNA primer-binding site (PBS) sequence comprises 18 nucleotides which are complementary to those at the 3' end of the replication initiation primer tRNA(3Lys). To investigate the role of the PBS in viral replication, we either deleted the original wild-type PBS (complementary to tRNA(3Lys) or replaced it with DNA sequences complementary to either tRNA(1,2Lys) or tRNA(Phe). Transfection of COS cells with such molecular constructs yielded similar levels of viral progeny that were indistinguishable with regard to viral proteins and tRNA content. Virus particles derived from PBS-deleted molecular clones were noninfectious for MT-4, Jurkat, and CEM-T4 cells. However, infectious viruses were derived from constructs in which the PBS had been altered to sequences complementary to either tRNA(1,2Lys) or tRNA(Phe), although mutated forms showed significant lags in replication efficiency in comparison with wild types. Molecular analysis of reverse-transcribed DNA in cells infected by the mutated viruses indicated that both tRNA(1,2Lys) and tRNA(Phe) could function as primers for reverse transcription during the early stages of infection. Sequencing of full-length proviral DNA, obtained 6 days after infection, revealed the mutated PBS, indicating that a complete cycle of reverse transcription had occurred. During subsequent rounds of infection, reversion of the mutated PBS to wild-type sequences was observed, accompanied by increased production of viral gene products. Reversion to wild-type PBS sequences was confirmed both by specific PCR analysis, using distinct primer pairs, and by direct sequencing of amplified segments. We also performed endogenous in vitro reverse transcription experiments in which synthesis of minus-strand strong-stop viral DNA was primed from a synthetic RNA template containing a PBS complementary to various tRNA isoacceptors. These results showed that tRNA(3Lys) was a much more efficient primer of such reactions than either tRNA(1,2Lys) or tRNA(Phe).

The A-rich RNA sequences of HIV-1 pol are important for the synthesis of viral cDNA

The bias of A-rich codons in HIV-1 pol is thought to be a record of hypermutations in viral genomes that lack biological functions. Bioinformatic analysis predicted that A-rich sequences are generally associated with minimal local RNA structures. Using codon modifications to reduce the amount of A-rich sequences within HIV-1 genomes, we have reduced the flexibility of RNA sequences in pol to analyze the functional significance of these A-rich ‘structurally poor’ RNA elements in HIV-1 pol. Our data showed that codon modification of HIV-1 sequences led to a suppression of virus infectivity by 5–100-fold, and this defect does not correlate with, viral entry, viral protein expression levels, viral protein profiles or virion packaging of genomic RNA. Codon modification of HIV-1 pol correlated with an enhanced dimer stability of the viral RNA genome, which was associated with a reduction of viral cDNA synthesis both during HIV-1 infection and in a cell free reverse transcription assay. Our data provided direct evidence that the HIV-1 A-rich pol sequence is not merely an evolutionary artifact of enzyme-induced hypermutations, and that HIV-1 has adapted to rely on A-rich RNA sequences to support the synthesis of viral cDNA during reverse transcription, highlighting the utility of using ‘structurally poor’ RNA domains in regulating biological process.

Selectivity in separation using π electron-rich stationary phases for the comprehensive two-dimensional analysis of cafe espresso

The multidimensional high-performance liquid chromatography separations of the complex sample matrix found in café espresso coffee were completed on the propyl phenyl and butyl phenyl columns that contain 3 and 4 carbon atoms in the spacer chain, respectively. Phenyl type stationary phases are able to undergo unique π–π interactions with aromatic compounds. Previous works have found that there are differences in retention characteristics between these chain lengths and this was explored further here. It was found that when analysing the separations by quadrants, using a geometric approach to factor analysis and by measuring the normalised mean radius, subtle differences in the separations were observed and the butyl phenyl phase was more selective for the high to medium polarity species. However, there was very little difference in separation behaviour for the hydrophobic components within the coffee sample. Overall, the analysis of the entire separation showed very little difference.