相補的配列

WordNet

determine the order of constituents in; "They sequenced the human genome"
a following of one thing after another in time; "the doctor saw a sequence of patients" (同)chronological sequence, succession, successiveness, chronological succession
film consisting of a succession of related shots that develop a given subject in a movie (同)episode
serial arrangement in which things follow in logical order or a recurrent pattern; "the sequence of names was alphabetical"; "he invented a technique to determine the sequence of base pairs in DNA"
several repetitions of a melodic phrase in different keys
arrange in a sequence
of words or propositions so related that each is the negation of the other; "`male and `female are complementary terms"

PrepTutorEJDIC

〈U〉〈C〉(時間の上の,また因果関係のつながりによる)『連続』,続き / 〈C〉《a~》(…の)一連のもの《+『of』+『名』》 / 〈U〉(起こる)『順序』(order),筋道 / 〈C〉(…に対する)結果《+『to』+『名』》
補足的な,補充する
配列,接続;(特に時間の)調整

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2013/03/07 22:47:35」(JST)

wiki en

[Wiki en表示]

For complementary sequences in biology, see complementarity (molecular biology).

In applied mathematics, complementary sequences (CS) are pairs of sequences with the useful property that their out-of-phase aperiodic autocorrelation coefficients sum to zero. Binary complementary sequences were first introduced by Marcel J. E. Golay in 1949. In 1961–1962 Golay gave several methods for constructing sequences of length 2^N and gave examples of complementary sequences of lengths 10 and 26. In 1974 R. J. Turyn gave a method for constructing sequences of length mn from sequences of lengths m and n which allows the construction of sequences of any length of the form 2^N10^K26^M.

Later the theory of complementary sequences was generalized by other authors to polyphase complementary sequences, multilevel complementary sequences, and arbitrary complex complementary sequences. Complementary sets have also been considered; these can contain more than two sequences.

Definition

Let (a₀, a₁, ..., a_N − 1) and (b₀, b₁, ..., b_N − 1) be a pair of bipolar sequences, meaning that a(k) and b(k) have values +1 or −1. Let the aperiodic autocorrelation function of the sequence x be defined by

Then the pair of sequences a and b is complementary if:

for k = 1, ..., N − 1.

Or using Kronecker delta we can write:

where C is a constant.

So we can say that the sum of autocorrelation functions of complementary sequences is a delta function which is an ideal autocorrelations for many applications like radar pulse compression and spread spectrum telecommunications.

Examples

As the simplest example we have sequences of length 2: (+1, +1) and (+1, −1). Their autocorrelation functions are (2, 1) and (2, −1), which add up to (4, 0).
As the next example (sequences of length 4), we have (+1, +1, +1, −1) and (+1, +1, −1, +1). Their autocorrelation functions are (4, 1, 0, −1) and (4, −1, 0, 1), which add up to (8, 0, 0, 0).
One example of length 8 is (+1, +1, +1, −1, +1, +1, −1, +1) and (+1, +1, +1, −1, −1, −1, +1, −1). Their autocorrelation functions are (8, −1, 0, 3, 0, 1, 0, 1) and (8, 1, 0, −3, 0, −1, 0, −1).
An example of length 10 given by Golay is (+1, +1, −1, +1, −1, +1, −1, −1, +1, +1) and (+1, +1, −1, +1, +1, +1, +1, +1, −1, −1). Their autocorrelation functions are (10, −3, 0, −1, 0, 1,−2, −1, 2, 1) and (10, 3, 0, 1, 0, −1, 2, 1, −2, −1).

Properties of complementary pairs of sequences

Complementary sequences have complementary spectra. As the autocorrelation function and the power spectra form a Fourier pair complementary sequences also have complementary spectra. But as the Fourier transform of a delta function is a constant we can write

where C_S is a constant.

S_a and S_b are defined as a squared magnitude of the Fourier transform of the sequences. The Fourier transform can be a direct DFT of the sequences, it can be a DFT of zero padded sequences or it can be a continuous Fourier transform of the sequences which is equivalent to the Z transform for Z = e^jω.

CS spectra is upper bounded. As S_a and S_b are non-negative values we can write

also

If any of the sequences of the CS pair is inverted (multiplied by −1) they remain complementary. More generally if any of the sequences is multiplied by e^jφ they remain complementary;
If any of the sequences is reverted (inverted in time) they remain complementary;
If any of the sequences is delayed they remain complementary;
If the sequences are interchanged they remain complementary;
If both sequences are multiplied by the same constant (real or complex) they remain complementary;
If both sequences are decimated in time by K they remain complementary. More precisely if from a complementary pair ((a(k), b(k)) we form a new pair (a(Nk), b(N*k)) with zero samples in between then the new sequences are complementary.
If alternating bits of both sequences are inverted they remain complementary. In general for arbitrary complex sequences if both sequences are multiplied by e^jπkn/N (where k is a constant and n is the time index) they remain complementary
A new pair of complementary sequences can be formed as [a b] and [a −b] where [..] denotes concatenation and a and b are a pair of CS;
A new pair of sequences can be formed as {a b} and {a −b} where {..} denotes interleaving of sequences.
A new pair of sequences can be formed as a + b and a − b.

Golay pair

A complementary pair a, b may be encoded as polynomials A(z) = a(0) + a(1)z + ... + a(N − 1)z^N−1 and similarly for B(z). The complementarity property of the sequences is equivalent to the condition

for all z on the unit circle, that is, |z| = 1. If so, A and B form a Golay pair of polynomials. Examples include the Shapiro polynomials, which give rise to complementary sequences of length a power of 2.

Applications of complementary sequences

Multislit spectrometry
Ultrasound measurements
Acoustic measurements
radar pulse compression
Wi-Fi networks,
3G CDMA wireless networks
OFDM communication systems
Train wheel detection systems
Non-destructive tests (NDT)
Communications

References

M.J.E. Golay (1949). "Multislit spectroscopy". J. Opt. Soc. Amer. 39: 437–444.
M.J.E. Golay (April 1961). "Complementary series". IRE Trans. Inform. Theory IT-7: 82–87.
M.J.E. Golay (1962). "Note on “Complementary series″". Proc. IRE 50: 84.
R.J. Turyn (1974). "Hadamard matrices, Baumert-Hall units, four-symbol sequences, pulse compression, and surface wave encodings". J. Combin. Theory (A) 16 (3): 313–333. doi:10.1016/0097-3165(74)90056-9.
Peter Borwein (2002). Computational excursions in probability and number theory. CMS Books in Mathematics. Springer-Verlag. pp. 110–119. ISBN 0-387-95444-9.
P.G. Donato; J. Ureña; M. Mazo; C. De Marziani; A. Ochoa (2006). "Design and signal processing of a magnetic sensor array for train wheel detection". Sensors and Actuators A: Physical 132 (2): 516–525. doi:10.1016/j.sna.2006.02.043.

UpToDate Contents

全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.

1. 遺伝性疾患の基本原則 basic principles of genetic disease
2. リウマチ性疾患に対する補完・代替療法 complementary and alternative remedies for rheumatic disorders
3. 小児における補完剤および代替剤の概要 overview of complementary and alternative medicine in pediatrics
4. 成人における迅速導入気管挿管のための前処置剤 pretreatment agents for rapid sequence intubation in adults
5. 成人における迅速導入気管挿管 rapid sequence intubation in adults

English Journal

Isothermal and rapid detection of pathogenic microorganisms using a nano-rolling circle amplification-surface plasmon resonance biosensor.

Shi D1, Huang J1, Chuai Z1, Chen D1, Zhu X1, Wang H1, Peng J1, Wu H1, Huang Q2, Fu W3.
Biosensors & bioelectronics.Biosens Bioelectron.2014 Dec 15;62:280-7. doi: 10.1016/j.bios.2014.06.066. Epub 2014 Jul 5.
Rolling circle amplification (RCA) of DNA is a sensitive and cost effective method for the rapid identification of pathogens without the need for sequencing. In this study, a surface plasmon resonance DNA biosensor based on RCA with a gold (Au) nanoparticle surface was established for isothermal ide
PMID 25022511

Direct, sequence-specific detection of dsDNA based on peptide nucleic acid and graphene oxide without requiring denaturation.

Lee J1, Park IS1, Jung E2, Lee Y2, Min DH3.
Biosensors & bioelectronics.Biosens Bioelectron.2014 Dec 15;62:140-4. doi: 10.1016/j.bios.2014.06.028. Epub 2014 Jun 20.
Sequence-specific detection of double stranded DNA (dsDNA) is important in various research fields. In general, denaturation of dsDNA into single strands is necessary for the sequence-specific recognition of probes to target DNA, posing several drawbacks which decrease the efficiency as a DNA sensor
PMID 24997367

DNA-length-dependent fluorescent sensing based on energy transfer in self-assembled multilayers.

Sun XY1, Liu B2, Sun YF2, Yu Y2.
Biosensors & bioelectronics.Biosens Bioelectron.2014 Nov 15;61:466-70. doi: 10.1016/j.bios.2014.05.055. Epub 2014 Jun 4.
In this paper, a novel DNA-length-dependent fluorescent sensor was constructed based on the fluorescence resonance energy transfer. In the self-assembled multilayers (Quartz/GO/PDDA/Tx-DNA/PDDA/ZnO@CdS), ZnO@CdS and graphene oxide(GO) were employed as an energy donor and an energy acceptor, respecti
PMID 24934748

Japanese Journal

A note on the incidence of reverse complementary fungal ITS sequences in the public sequence databases and a software tool for their detection and reorientation

HENRIK NILSSON R.,VELDRE Vilmar,WANG Zheng,ECKART Martin,BRANCO Sara,HARTMANN Martin,QUINCE Christopher,GODHE Anna,BERTRAND Yann,ALFREDSSON Johan F.,LARSSON Karl-Henrik,KOLJALG Urmas,ABARENKOV Kessy
Mycoscience 52(4), 278-282, 2011-07-25
NAID 10029296602

A Viral Satellite RNA Induces Yellow Symptoms on Tobacco by Targeting a Gene Involved in Chlorophyll Biosynthesis using the RNA Silencing Machinery

Shimura Hanako,Pantaleo Vitantonio,Ishihara Takeaki,Myojo Nobutoshi,Inaba Jun-ichi,Sueda Kae,Burgyán József,Masuta Chikara
PLoS Pathogens 7(5), e1002021, 2011-05-05
… We found that the mRNA of tobacco magnesium protoporphyrin chelatase subunit I (ChlI, the key gene involved in chlorophyll synthesis) had a 22-nt sequence that was complementary to the Y-sat sequence, including four G-U pairs, and that the Y-sat-derived siRNAs in the virus-infected plant downregulate the mRNA of ChlI by targeting the complementary sequence. …
NAID 120003059662