We describe a new family of unimodular almost two-valued periodic Golay sequence pairs of length p, where p is an odd prime. The sequences are obtained from the Legendre symbol by replacing the letters$0, 1, -1$with the letters$1, A, B\in \Bbb {C}$,$|A|=|B|=1$, where B additionally satisfies an appropriate constraint. The family is infinite in that each value of A yields at least one Golay pair or an ideal sequence. In special cases the family includes: 1) sequences with$A=1$, or$B=\pm \bar {A}$, or$B=\pm i\bar {A}$, or where both A and B are Gaussian rationals, or roots of unity; and 2), sequences whose autocorrelation sidelobes approach zero as p approaches infinity. These results extend the results of Björck on two-valued/almost two-valued ideal sequences derived from cyclic p-roots and the results of Golomb on two-valued ideal sequences derived from Hadamard-Paley difference sets. Related, but in some ways more constrained results on two-valued Golay sequence pairs derived from difference set families were recently published by Li et al.

Using elementary properties of primitive multiplicative characters we derive the autocorrelation of a unimodular$M$-ary character-based sequence of length$pq$, where$p$and$q$are distinct odd primes. Subsequently: (1) we identify three new sets of twin-prime quadriphase sequences with the largest autocorrelation sidelobe magnitude equal to$\sqrt {5}$or 3, (2) we show that the smallest maximum autocorrelation sidelobe magnitude of an$M$-ary character-based sequence, when$4|M$, either decreases with$M$and tends to 2, when$6\nmid M$, or is equal to 2, when$6|M$, and (3), we show that the smallest maximum autocorrelation sidelobe magnitude of a full-alphabet$M$-ary character-based sequence, where$M>2$, is greater or equal to$\sqrt {3}$, and, in particular, is equal to$\sqrt {3}$for the sextic phase sequence.

This paper describes a KM2×M, K ∈ Q, M, KM ∈ Z, Zak space construction of zero correlation zone polyphase sequence sets, of sequence length KM3and set size KM, with all-zero cross correlation. The construction includes the sets with an (M-1)-point and (T2M-1)-point zero autocorrelation zone, where T2is an arbitrary nontrivial factor of M. All sequences in these sets have sparse, highly structured, semipolyphase finite Zak transforms, with constant nonzero magnitude at M points and zero magnitude at selectable KM3-M points, and sparse, semipolyphase KM3-point discrete Fourier transforms, with constant nonzero magnitude at M2points and zero magnitude at selectable KM3-M2points.

This work describes an M2× M Zak space construction of new zero correlation zone polyphase sequence sets, of sequence length M3and set size M, with all-zero cross-correlation. The construction includes the sets with (M-1)-point, (T2M-1)-point and (M2-1)-point zero auto correlation zone, where T2is an arbitrary non-trivial factor of M. All sequences in these sets have sparse discrete Fourier transforms with constant non-zero magnitude at M2points and zero magnitude at (M -1)M2points.

Availability of DNA data is growing roughly at the rate specified by Moore's law. In many molecular biology applications this data must be compared with a reference sequence, either to establish similarity of genomes or to identify functionally homologous subsequences. Current approaches based on pair-wise sequence alignments are computationally expensive and often data dependent. To ameliorate this problem, alternative, less complex sequence comparison schemes, designed to capture the essential features of genomes, must be explored. In this work a new sequence comparison approach, based on difference set models, is proposed. These models are conceptually appropriate, as they quantify, in a certain sense, two key genome attributes: sequence complexity and symbol repetition. Moreover, it is shown that difference sets are abundant in bacterial genomes and that they coincide with homologous sequence segments. These findings motivate the construction of compact representations of DNA sequences in the difference set space. An alignment of these representations permits computationally efficient identification of differences between the DNA sequences. To illustrate the efficacy of the difference set approach, characterization of indels in closely relatedbacillus anthracisstrains is performed, resulting in the discovery of two previously unreported collections of polymorphisms. In addition to these results, an open problem of extending the difference set approach to difference set and almost difference set families, for the analysis of more distant DNA sequences, is discussed.

Dempster-Shafer theory is one of the main tools for reasoning about data obtained from multiple sources, subject to uncertain information. In this work abstract algebraic properties of the Dempster-Shafer set of mass assignments are investigated and compared with the properties of the Bayes set of probabilities. The Bayes set is a special case of the Dempster-Shafer set, where all non-singleton masses are fixed at zero. The language of semigroups is used, as appropriate subsets of the Dempster-Shafer set, including the Bayes set and the singleton Dempster-Shafer set, under either a mild restriction or a slight extension, are semigroups with respect to the Dempster-Shafer evidence combination operation. These two semigroups are shown to be related by a semigroup homomorphism, with elements of the Bayes set acting as images of disjoint subsets of the Dempster-Shafer set. Subsequently, an inverse mapping from the Bayes set onto the set of these subsets is identified and a procedure for computing certain elements of these subsets, acting as subset generators, is obtained. The algebraic relationship between the Dempster-Shafer and Bayes evidence accumulation schemes revealed in the investigation elucidates the role of uncertainty in the Dempster-Shafer theory and enables direct comparison of results of the two analyses.

Previously, a discretization of the linear FM chirp of lengthN=KL2,LandKLisin Z, was given and the conditions for its minimal Zak space support were derived. Chirps satisfying these conditions are known as finite chirps. In this work, subsets of finite chirps of lengthN=L2,La prime, are examined. The investigation leads to a new, Zak space construction of general polyphase sequence sets of sizeL-1 with optimal auto and cross-correlation properties, known as perfect sequence sets. It is shown that perfect sequence sets are closely related to sets of finite chirps and, in particular, include the sets of Zadoff-Chu sequences (which are identical with subsets of finite chirps) and the sets of generalized Frank sequences (which are identical with sets of modulations of finite chirps), as special cases. The entire collection of perfect sequence sets is then given by a partition of the set of perfect auto correlation sequences, obtained by right coset decomposition of the group of all permutations with respect to a certain cyclic group. The construction suggests several further generalizations that can be obtained by operating exclusively on subgroups of the permutation group.

MOTIVATION: One of the main tasks of DNA sequence analysis is identification of repetitive patterns. DNA symbol repetitions play a key role in a number of applications, including prediction of gene and exon locations, identification of diseases, reconstruction of human evolutionary history and DNA forensics. RESULTS: A new approach towards identification of tandem repeats in DNA sequences is proposed. The approach is a refinement of previously considered method, based on the complex periodicity transform. The refinement is obtained, among others, by mapping of DNA symbols to pure quaternions. This mapping results in an enhanced, symbol-balanced sensitivity of the transform to DNA patterns, and an unambiguous threshold selection criterion. Computational efficiency of the transform is further improved, and coupling of the computation with the period value is removed, thereby facilitating parallel implementation of the algorithm. Additionally, a post-processing stage is inserted into the algorithm, enabling unambiguous display of results in a convenient graphical format. Comparison of the quaternionic periodicity transform with two well-known pattern detection techniques shows that the new approach is competitive with these two techniques in detection of exact and approximate repeats.

General conditions are derived for an (N=KL2)-point discrete chirp with chirp rate a and carrier frequency b to have minimal support on the LtimesKL Zak transform lattice. Earlier, it has been shown that when the normalized chirp parameters amacr= aK, amacr= aK2, and 2bmacr = 2bK are integers, the last two of the same parity, then the discrete chirp is supported at KL points. Here, this condition is relaxed, by allowing amacr to be a rational number, i.e., amacr = n/d, n, disin Z, (n,d)=1, and requiring only that amacr and bmacrL be integers of arbitrary parity. It is shown that the support of the Zak space chirp satisfying the new condition then increases to dKL points. The results provide foundations for future constructions of sophisticated radar and communications signal processing algorithms. Examples of direct applications of the Zak space conditions in chirp parameter estimation, chirp detection, and chirp de-noising are included

In the above titled paper (ibid., vol. 53, pp. 2190-2203, Jun 07), equation (B6) in Appendix B incorrectly identifies the Jacobi symbol. The proper definition is provided here.

In this letter, closed-form expressions for the discrete Fourier transform (DFT) of a finite chirp are derived. It is shown that when the normalized chirp rate is coprime with the chirp length, then the DFT of a finite chirp is again a finite chirp with magnitude, chirp rate, and carrier frequency appropriately scaled. In particular, when the normalized chirp rate is of unit value, then the DFT of a finite chirp is the same chirp, up to a complex scaling factor. Conversely, when the normalized chirp rate has a common factor with the chirp length, then the support of the DFT of a finite chirp is equal to the ratio of chirp length and the common factor. Among other things, results given here complement certain results, obtained by Janssen, on the computation of time-continuous chirps with rational sweep rates

A new approach towards computing the periodicity transform of DNA sequences is proposed. The approach is based on the mapping of DNA symbols to pure quaternions. The resulting quaternionic periodicity transform outperforms the previously proposed complex periodicity transform due to enhanced, symbol-balanced sensitivity to DNA patterns. The theoretical finding is supported by a performance comparison of the two transforms and by an application example.