하다마드 변형

부울 함수와 월시 행렬의 산물은 월시 스펙트럼이다.^[1]
(1, 0, 0, 0, 1, 0) × H(8) = (4, 2, 0, -2, 0, 0, 0, 0, 2)

Fast Walsh-Hadamard 변환, (1, 0, 1, 0, 0)의 월시 스펙트럼을 계산하는 더 빠른 방법이다.

원래 함수는 산술 다항식으로서 월시 스펙트럼을 이용하여 표현할 수 있다.

하다마드 변환(Walsh-Hadamard 변환, Hadamard-Rademacher-Walsh 변환, Walsh 변환 또는 Walsh-Fourier 변환이라고도 한다)은 푸리에 변환의 일반화된 클래스의 예다. 그것은 직교, 대칭, 비자발적, 선형 연산을 $2개$ 의^m 실수(또는 복잡한 수, 또는 하이퍼 복합 수, 비록 Hadamard 행렬 자체는 순수하게 실제 수이다)에 대해 수행한다.

Hadamard 변환은 크기-2 이산 푸리에 변환(DFT)으로 구축된 것으로 간주할 수 있으며, 사실 크기 $2 \times$ 2× × × × $2$ 의 다차원 DFT와 동등하다.^[2] 임의 입력 벡터를 월시 함수의 중첩으로 분해한다.

이 변형은 프랑스 수학자 자크 하다마르(프랑스어: [adamaʁ]), 독일계 미국인 수학자 한스 라데마허(Hans Rademacher), 미국 수학자 조셉 L. Walsh의 이름을 따서 명명되었다.

정의

Hadamard 변환 H는_m 2^m × 2 행렬인^m Hadamard 행렬(정규화 인자에 의해 크기가 조정됨)으로, 2개의^m 실수 x를_n 2개의^m 실수 X로_k 변환한다. Hadamard 변환은 두 가지 방법으로 정의될 수 있다: 재귀적으로 또는 지수 n과 k의 이진(베이스-2) 표현을 사용하여.

반복적으로 1₀ × 1 Hadamard 변환 H를₀ ID H = 1로 정의한 후, m > 0에 대해 H를 다음과_m 같이 정의한다.

H_{m}={\frac {1}{\\sqrt{2}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}

여기서 1/4.2는 때때로 생략되는 정규화다.

m > 1의 경우 H를 다음과_m 같이 정의할 수도 있다.

H_{m}=H_{1}\otimes H_{m-1

여기서 $\otimes$ $\otimes$ 은(는) Kronecker 제품을 나타낸다 $\otimes$ . 따라서 이 정규화 요인 외에 Hadamard 행렬은 전적으로 1과 -1로 구성된다.

마찬가지로, 우리는 (k, n)-th 항목으로 Hadamard 행렬을 정의할 수 있다.

{\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\cdots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\cdots +n_{1}2+n_{0}\end{aligned}}

여기서 k와_j n은_j 각각 k와 n의 비트 요소(0 또는 1)이다. 왼쪽 상단 모서리에 있는 요소의 경우 $k=n=0$ = n $k=n=0$ = $k=n=0$ $k=n=0$ 을(를) 정의하며 $k=n=0$ 이 경우 다음이 있다.

(H_{m}_{k,n}={\frac {1}{2^{m/2}}(-1)^{\sum _{j}k_{j}n_{j}}}}}}

이것은 정확히 다차원 ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ × ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ 2 × 2 ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ × 텍스트 $스타일$ 2 $\time$ 2\time 2 $\time$ 2 $\time$ 2\ $time$ 2 $DFT$ 로 ${\textstyle 2\times 2\times \cdots \times 2\times 2}$ , 입력과 출력이 n과_j_j k에 의해 각각 지수화된 다차원 배열로 간주되는 경우 단일으로 정규화된 것이다.

Hadamard 행렬의 몇 가지 예는 다음과 같다.

비트{\required}H_{0}&=+{\begin{pmatrix}{\begin{array}{r}1\end{pmatrix}\[5pt]H_{1}&={\frac {1}{\sqrt{2}}:{\begin{pmatrix}{\begin{pmatrix}{rrr}1&\\1&-1\end{pt}\end{pmatrix}}\[5pt]H_{2}&={\frac{1}:{2}}:{\begin{pmatrix}{\begin{pmatrix}{rrrr}1&1&1&1\\\1&1&1&-1\\\1&1&1&1&1\end{pmatrix\nd}{pt]H_{3}&, ={\frac{1}{2^{3/2}}}{\begin{pmatrix}{\begin{배열}{rrrrrrrr}1&, 1&, 1&, 1&, 1&, 1&, 1&, 1\\1&, -1&, 1&, -1&, 1&, -1&, 1&, -1\\1&, 1&, -1&, -1&, 1&, 1&, -1&, -1\\1&, -1&, -1&, 1&, 1&, -1&, -1&, 1\\1&, 1&, 1&, 1&, -1&, -1&, -1&, -1\\1&, -1&, 1&, -1&, -1&, 1&-1&, 1\\1&, 1&, -1&, -1&, -1&, -1&, 1&, 1\\1&, -1&, -1&, 1&, -1&, 1&, 1&, -1\end{배열}}\end{pmatrix}}\\[5pt](H_{n}_{i,j}&={\frac {1}{2^{n/2}}(-1)^{i\cdot j}\end{aigned}}}}}

여기서 $i\cdot j$ $i\cdot j$ $i\cdot j$ $i\cdot j$ 은 $i\cdot j$ 숫자 i와 j의 이진 표현에 대한 비트 도트 제품이다. For example, if ${\textstyle n\;\geq \;2}$ , then ${\textstyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$ , agreeing with the above (ignoring the 전체 상수). 첫 번째 행, 매트릭스의 첫 번째 열 요소는 ${\textstyle (H_{n})_{0,0}}$ ( ${\textstyle (H_{n})_{0,0}}$ ) 0 ${\textstyle (H_{n})_{0,0}}$ ${\textstyle (H_{n})_{0,0}}$ ${\$ 로 표시된다는 점에 유의하십시오 ${\textstyle (H_{n})_{0,0}}$

H는₁ 정확히 크기가 2 DFT이다. 또한 Z/(2)의 2요소 첨가물 그룹에서 푸리에 변환으로 간주할 수 있다.

Hadamard 행렬의 행은 월시함수다.

월시-하다마드 변환의 장점

진짜

위의 행렬 H의 정의에 따라 H = H[m,n]를 허용한다.

H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}

월시 변환에서는 행렬에 1과 –1만 나타난다. 1과 –1의 숫자가 실수로 되어 있어 불합리한 숫자 계산을 사용할 필요가 없다.

곱셈이 필요하지 않음

DFT는 비합리적인 곱셈이 필요한 반면, Hadamard 변환은 그렇지 않다. 간판만 뒤집으면 되기 때문에 합리적인 곱셈도 필요 없다.

일부 속성은 DFT의 속성과 유사하다.

월시 변환에서 첫 번째 행렬 행의 모든 숫자는 1과 같다.

{\reasoned}H[m,n]=&,{\begin{pmatrix}{\begin{배열}{rrrrrrrr}1&, 1&, 1&, 1&, 1&, 1&, 1&, 1\\1&, 1&, 1&, 1&, -1&, -1&, -1&, -1\\1&, 1&, -1&, -1&, -1&, -1&, 1&, 1\\1&, 1&, -1&, -1&, 1&, 1&, -1&, -1\\1&, -1&, 1&, 1&, 1&, -1&, -1&, 1\\1&, -1&, 1&, 1&, -1&, 1&, 1&, -1\\1&, -1&a융점, -1&, -1&, -1&, 1&, -1&, 1\\1&, -1&, -1&, -1&, 1&, -1&, 1&, -1\end{배열}}\end{pmatrix}}\\\end{정렬}}

이산 푸리에 변환:

e^{-j2\pi mN/N

이산 푸리에 변환에서 m이 0(첫 번째 행에 0)과 같을 때 DFT의 결과도 1이다. 두 번째 행에서는 첫 번째 행과 다르지만 첫 번째 원시 행렬의 신호가 저주파이며 두 번째 원시 행렬에서 주파수를 증가시키고 마지막 원시 행까지 주파수를 증가시킨다는 행렬의 특성을 관찰할 수 있다.

0 교차를 계산하는 경우:

         첫 번째 원시 = 0 교차, 두 번째 원시 = 1 0 교차, 세 번째 원시 = 2 0 교차. . 여덟 개의 원시 = 7 0 교차

푸리에 변환과의 관계

Hadamard 변환은 사실 크기 2×2×× × × $2$ 의 다차원 DFT와 동등하다.^[2]

또 다른 접근은 부울 집단을 푸리에 변환으로 한정된(abelian)그룹에 대한 푸리에 변환을 사용하여[4]n{\displaystyle(\mathbb{Z}/2\mathbb{Z})^{n}}.[3](Z/2Z)은 아다마르 변환을 보기 함수 f:(Z/2Z)n의 푸리에 변환 → C{\displaystyle f\colon(\mathbb{Z은}/2\m $atsb {Z}^{n}\to \mathb {C}}$ 은(는) 다음에 의해 정의된 ${\widehat {f}}$ 함수 $^$ {\ $displaystyle$ {\ $widehat$ { $f}}$ 이다 $f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C}$ .

{\widehat{f}(\chi )=\sum _{a\in(\mathb {Z} /2\mathb {Z} )^{n}f(a){\bar {\chi }}}

where $\chi$ is a character of $(\mathbb {Z} /2\mathbb {Z} )^{n}$ . Each character has the form $\chi _{r}(a)=(-1)^{a\cdot r}$ for some $r\in (\mathbb {Z} /2\mathbb {Z} )^{n}$ $r\in (\mathbb {Z} /2\mathbb {Z} )^{n}$ , where the multiplication is the boolean dot product on bit strings, so we can identify the input to ${\widehat {f}}$ with $r\in (\mathbb {Z} /2\mathbb {Z} )^{n}$ (Pontryagin duality) and define ${\displaystyle {\wideha$ $t {f}\colon(\mathb {Z} /2\mathb {Z} )^{n}\to \mathb {C}$ } by ${\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C}$ \mathb {C}

{\widehat{f}(r)=\sum _{a\in(\mathb {Z} /2\mathb {Z} )^{n}f(a)(-1)^{r\cdot a}}}

$f$ 은 f $f$ 및 $f$ ${\widehat {f}}$ ${\widehat {f}}$ ${\$ 에 대한 입력을 부울 문자열로 ${\widehat {f}}$ $f$ 하는 f{\ $displaystyle f}$ 의 Hadamard 변환이다 $f$

Hadamard 변환이 Hadamard $H_{n}$ $H_{n}$ ${\$ $displaystyle H_{$ n}에 의해 $v$ $v$ 에 $2^{n}$ $2^{n}$ 2n{\ $displaystyle$ v}의 벡터를 곱하는 위 공식의 관점에서, 동등성은 $H_{n}$ 해당 t에 해당하는 비트 문자열을 입력하기 위해 $f$ $f$ $f$ 을 취함으로써 나타난다.o $v$ $v$ 의 요소 인덱스 및 $f$ $f$ 이 $f$ $v$ 가) $v$ $v$ 의 해당 요소를 출력하도록 함 $v$

이를 $2^{n}$ ${\$ 복합 숫자의 $v$ $벡터$ v $v$ 에 적용할 때 주기 그룹 $\mathbb {Z} /2^{n}\mathbb {Z}$ / $\mathbb {Z} /2^{n}\mathbb {Z}$ Z ${\$ 의 $2^{n}$ 문자를 사용하는 일반적인 이산 푸리에 변환과 비교해 보십시오 $\mathbb {Z} /2^{n}\mathbb {Z}$

계산 복잡성

고전적 영역에서 Hadamard 변환은 고속 Hadamard 변환 알고리즘을 사용하여 $n=2^{m}$ $n\log n$ $n\log n$ ${\displaystyle$ n $\logn}$ 연산 $n\log n$ ( $n=2^{m}$ = $n=2^{m}$ ${\$ 으로 계산할 수 있다.

양자 영역에서, Hadamard 변환은 병렬화가 가능한 양자 논리 게이트인 $O(1)$ O $O(1)$ ( $O(1)$ ) ${\displaystyle$ O $(1)}$ 번으로 $O(1)$ 계산할 수 있다.

양자 컴퓨팅 애플리케이션

Hadamard 변환은 양자 컴퓨팅에 광범위하게 사용된다. 2 × 2 Hadamard 변환 $H_{1}$ 1 ${\$ }는 Hadamard 게이트로 알려진 양자 논리 게이트로 $H_{1}$ , n-qubit 레지스터의 각 쿼빗에 Hadamard 게이트를 병렬로 적용하는 것은 Hadamard 변환 H $H_{n}$ ${\$ 에 해당한다 $H_{n}$

하다마드 게이트

양자 컴퓨팅에서 Hadamard 게이트는 1쿼트의 회전으로, 계산 기준의 동일한 가중치를 $|0\rangle$ 2개의 중첩 상태에 $|1\rangle$ 쿼비트 베이스 상태 $|0\rangle$ $|0\rangle$ ${\displaystyle$ 0 $\rangele$ $}$ 과 $|0\rangle$ 1 $|0\rangle$ $|1\rangle$ $|1\rangle$ ${\displaystyle 1\rangele$ $}$ 을 매핑한다. $e$ 보통 다음 단계를 선택하여

H={\frac { 0\rangele + 1\rangle }{\sqrt {2}}\langle 0}\langle 0 +\frac {0\langle - 1\langle }{\sqrt {2}}\langle 1}}}}

디락 표기법으로 이것은 변환 매트릭스에 해당된다.

H_{1}={\frac {1}{\\sqrt{2}}:{\begin{pmatrix}1&1\1&-1\end{pmatrix}}}

계산 기준이라고도 하는 0 $|0\rangle ,|1\rangle$ $|0\rangle ,|1\rangle$ $0\rangele$ 기준 $|0\rangle ,|1\rangle$ . The states ${\textstyle {\frac {\left 0\right\rangle +\left 1\right\rangle }{\sqrt {2}}}}$ and ${\textstyle {\frac {\left 0\right\rangle -\left 1\right\rangle }{\sqrt {2}}}}$ are known as $\left {\boldsymbol {+}}\right\rangle$ and ${$ $\displaystyle \{\boardsymbol {-}\}\right\rangele }$ 이 $\left|{\boldsymbol {-}}\right\rangle$ (가) 각각 표시되며, 양자 컴퓨팅의 극적 기초를 구성한다.

하다마드 게이트 작전

{\reasoned}H(0\rangle)&, ={\frac{1}{\sqrt{2}}}0\rangle +{\frac{1}{\sqrt{2}}}1\rangle 단위:+\rangle \\H(1\rangle)&, ={\frac{1}{\sqrt{2}}}0\rangle -{\frac{1}{\sqrt{2}}}1\rangle 단위:-\rangle \\H\left({\frac{1}{\sqrt{2}}}0\rangle +{\frac{1}{\sqrt{2}}}1\rangle \right)&, ={\frac{1}{2}}{\Big(}0\rangle + 1\rangle{\Big)}+{\frac{1}{2}}{\B.ig(}0\rangle - 1\rangle {\Big )}= 0\rangle \\H\left({\frac {1}{\sqrt {2}}} 0\rangle -{\frac {1}{\sqrt {2}}} 1\rangle \right)&={\frac {1}{2}}{\Big (} 0\rangle + 1\rangle {\Big )}-{\frac {1}{2}}{\Big (} 0\rangle - 1\rangle {\Big )}= 1\rangle \end{aligned}}

Hadamard 게이트를 0 또는 1Qbit에 한 번 적용하면 양자 상태가 생성되며, 관측될 경우 동일한 확률을 가진 0 또는 1이 된다(초기 두 연산 참조). 이것은 계산의 표준 확률론적 모델에서 공정 동전을 뒤집는 것과 꼭 같다. 그러나 하다마드 게이트가 연속적으로 두 번 적용되면(마지막 두 번의 작업에서 효과적으로 수행되고 있는 것처럼), 최종 상태는 항상 초기 상태와 동일하다.

양자 알고리즘의 Hadamard 변환

양자 하다마드 변환을 계산하는 것은 단순히 하다마드 변환의 텐서형 제품 구조 때문에 각각의 쿼빗에 대해 개별적으로 하다마드 게이트를 적용하는 것이다. 이 간단한 결과는 양자 Hadamard 변환이 n log n 연산의 일반적인 경우와 비교하여 log n 연산을 필요로 한다는 것을 의미한다.

많은 $|0\rangle$ 알고리즘은 0 $|0\rangle ,|1\rangle$ ,, 1 $⟩,$ 1 ⟩, $|0\rangle ,|1\rangle$ {\ $displaystyle$ $0\rangele}$ 로 초기화된 m qubit를 동일한 $|0\rangle ,|1\rangle$ 으로 2개의 $|0\rangle ,|1\rangle$ 직교 상태의^m 중첩에 매핑하기 $|0\rangle$ 때문에 $초기$ 단계로 Hadamard 변환을 사용한다. 예를 들어, 이것은 독일-조즈사 알고리즘, 사이먼 알고리즘 , 번스타인-바지라니 알고리즘, 그로버 알고리즘에서 사용된다. Note that Shor's algorithm uses both an initial Hadamard transform, as well as the quantum Fourier transform, which are both types of Fourier transforms on finite groups; the first on $(\mathbb {Z} /2\mathbb {Z} )^{n}$ and the second on ${\displaystyle \mathbb {Z} /2^{n}\mathbb$ ${Z}$ .

분자 계통유전학(진화생물학) 응용

Hadamard 변환은 분자 데이터로부터 계통생성 나무를 추정하는데 사용될 수 있다.^[5]^[6]^[7] 계통유전학은 유기체 간의 관계를 이해하는 데 초점을 맞춘 진화생물학의 하위 분야다. DNA 다중 시퀀스 정렬에서 얻은 현장 패턴 주파수의 벡터(또는 매트릭스)에 적용된 Hadamard 변환을 사용하여 트리 위상에 대한 정보를 전달하는 또 다른 벡터를 생성할 수 있다. 또한 계통생성 하다마드 변환의 불변성을 통해 나무 위상 벡터에서 현장우도를 계산할 수 있어 계통생성 나무의 최대우도 추정에 하다마드 변환을 사용할 수 있다. 그러나 후자의 적용은 사이트 패턴 벡터에서 트리 벡터로 변환하는 것보다 덜 유용하다. 왜냐하면 훨씬 더 효율적인 사이트 가능성을^[8]^[9] 계산하는 다른 방법이 있기 때문이다. 그러나 계통생성 하다마드 변환의 불가역적인 성질은 수학 계통생식에 우아한 도구를 제공한다.^[10]^[11]

계통발생학 Hadamard 변환의 역학에는 현장 패턴 벡터 또는 행렬 $s(T)$ ) ${\displaystyle$ $T}$ 을(를 $)$ 사용하여 $T$ 트리 $T$ ${\$ displaystyle T $}$ 의 위상 및 가지 길이에 대한 정보를 제공하는 $\gamma (T)$ 벡터 vector $($ $\gamma (T)$ 의 계산이 포함된다 $s(T)$

\displaystyle \감마(T)=H^{-1}(\ln(Hs(T)))}

여기서 $H$ $H$ 은 $H$ (는) 적절한 크기의 Hadamard 행렬이다. 이 방정식은 해석을 단순화하기 위해 일련의 세 개의 방정식으로 다시 쓸 수 있다.

{\begin}r&=Hs(T)\\rho &\ln(T)\gamma(T)&=H^{-1}\rho \ended}}}

이 방정식의 되돌릴 수 없는 특성은 다음과 같이 예상 부지 패턴 벡터(또는 행렬)를 계산할 수 있다.

[\displaystyle s(T)=]H^{-1}(\exp(H\감마(T)))}

뉴클레오티드를 2진 문자로 부호화하여 DNA에 캐벤더-파리스-네이만(CFN) 2상태 대체 모델을 사용할 수 있다(청진 A와 G는 R로, 피리미딘 C와 T는 Y로 부호화된다). 이를 통해 다음 예시와 같이 다중 시퀀스 정렬을 트리 벡터 $\gamma (T)$ $\gamma (T)$ $displaystyle s(T)}$ 로 변환할 수 있는 사이트 $s(T)$ 패턴 벡터 $s(T)$ ( $s(T)$ ) $\gamma (T)$ 로 인코딩할 수 있다 $\gamma (T)$

특정 트리에 대한 Hadamard 변환의 예(Wadell et al. 1997에서^[12] 채택된 작업 예제의 값)

색인	이진 패턴	정렬 패턴	$\displaystyle \gamma(T)$	$\rho =H^{-1}\감마(T)$	$(\displaystyle r=\exp(\rho )}$	$[\displaystyle s(T)=]H^{-1}\rho }$
0	0000	RRRR 및 YYYY	−0.475	0	1	0.6479
1	0001	RRRY 및 YYR	0.2	−0.5	0.6065	0.1283
2	0010	RRYR과 YYRY	0.025	−0.15	0.8607	0.02
3*	0011	RRYY와 YYRR	0.025	−0.45	0.6376	0.0226
4	0100	RRRRY와 YRYY	0.2	−0.45	0.6376	0.1283
5*	0101	RYRY와 YRYR	0	−0.85	0.4274	0.0258
6*	0110	RYYR와 YRRY	0	−0.5	0.6065	0.0070
7	0111	RYYY와 YRRR	0.025	−0.9	0.4066	0.02

이 표에 표시된 예는 단순화된 3개의 방정식 체계를 사용하며, (A,B), (C,D)로 쓸 수 있는 (A,B), (C,D);;;로 쓸 수 있는 4개의 택슨 트리를 위한 것이다. 사이트 패턴은 ABCD 순서에 따라 작성된다. This particular tree has two long terminal branches (0.2 transversion substitutions per site), two short terminal branches (0.025 transversion substitutions per site), and a short internal branch (0.025 transversion substitutions per site); thus, it would be written as ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)); in newick format. 이 트리는 최대 구문 분석 기준을 사용하여 데이터를 분석하는 경우( $s(T)=H^{-1}\rho$ 된 시퀀스가 s $s(T)=H^{-1}\rho$ ( $s(T)=H^{-1}\rho$ ) $s(T)=H^{-1}\rho$ = $s(T)=H^{-1}\rho$ - $s(T)=H^{-1}\rho$ $s(T)=H^{-1}\rho$ ${\displaystyle s(T)=$ 에 표시된 예상 주파수에 근접할 정도로 충분히 길다고 가정할 때 긴 분기 매력을 나타낸다. $H^{-1}\rho }$ 열 $s(T)=H^{-1}\rho$ ). 긴 분기 어트랙션에는 트리를 지원하는 지수 6(A,C), 지수 B,D)의 예상 사이트 패턴 수가 트리를 지원하는 예상 사이트 패턴 수(지수 4)를 초과한다는 사실이 반영한다. 분명히 계통발생학 하다마드 변환의 불가역적 성질은 트리 벡터( $\gamma (T)$ vector $\gamma (T)$ $\gamma (T)$ (T $){\displaystyle \gamma (T)}$ 가 올바른 트리에 해당하는 $\gamma (T)$ 것을 의미한다는 것을 의미한다. 따라서 변환 후 구문 분석은 ^[13]정확한 모형을 사용한 표준 최대우도 분석처럼 통계적으로 일관된다(이 경우 CFN 모델).

0의 사이트 패턴은 변경되지 않은 사이트(뉴클레오티드를 청색 또는 피리미딘으로 인코딩한 후)에 해당한다는 점에 유의하십시오. 별표(3, 5, 6)를 갖는 지수는 "파시모니-정보적"이며, 나머지 지수는 단일 택슨이 다른 세 가지 세금과 다른 사이트 패턴을 나타낸다(따라서 표준 최대우도 계통생성 트리의 터미널 분기 길이와 동일).

R과 Y(그리고 궁극적으로 0과 1)로 재코딩하지 않고 뉴클레오티드 데이터를 사용하려는 경우 사이트 패턴을 매트릭스로 인코딩할 수 있다. 우리가 4-택손 나무를 고려한다면 총 256개의 현장 패턴이 있다(4차 전력에 대한 4개의 뉴클레오티드). 그러나 키무라 3-모수(또는 K81) 모델의 대칭은 DNA에 대한 256개의 가능한 현장 패턴을 64개의 패턴으로 줄일 수 있게 하여, 변환(RY) 사이트 패턴에 대해 위에서 사용한 8개 원소의 벡터와 유사한 방식으로 4-태손 트리의 뉴클레오티드 데이터를 8×8 행렬로^[14] 인코딩할 수 있게 한다. 이는 Klein 4-group을 사용하여 데이터를 재코딩함으로써 달성된다.

계통생성 Hadamard 변환을 위한 클라인 4그룹 코드화
뉴클레오티드 1	뉴클레오티드 2	뉴클레오티드 3	뉴클레오티드 4
A(0,0)	G(1,0)	C(0,1)	T(1,1)
C(0,0)	T(1,0)	A(0,1)	G(1,1)
G(0,0)	A(1,0)	T(0,1)	C(1,1)
T(0,0)	C(1,0)	G(0,1)	A(1,1)

RY 데이터와 마찬가지로 사이트 패턴은 임의로 선택한 첫 번째 세원의 베이스를 기준으로 인덱싱되고 그 첫 번째 베이스에 대해 인코딩된 후속 세자의 베이스를 기준으로 인덱싱된다. 따라서 첫 번째 세원은 비트 쌍(0,0)을 받는다. 이러한 비트 쌍을 사용하면 RY 벡터와 유사한 벡터 두 개를 생성하고 그 벡터를 사용하여 매트릭스를 채울 수 있다. 이는 4개의 영장류 헤모글로빈 유사 생물의 다중 시퀀스 정렬을 기반으로 하는 헨디 외 연구진(1994)의 예를 사용하여 설명할 수 있다.^[14]

인코딩된 시퀀스 정렬의 예(Hendy et al. 1994^[14])(값은 9879개 사이트 중 카운트)

	0	8	16	24	32	56
0	8988	9	10	12	24	90
1	41	9		**
2	45		13
3	54*			14		3
4	94				20
5			1
6	2				2
7	356		1		1	75

0열의 사이트 패턴 수가 훨씬 더 많은 것은 0열이 사실상 모든 게놈 영역의 비교에서 전이 차이보다 더 빠르게 축적되는 전환 차이(그리고 확실히 이 작업 예에^[15] 사용된 헤모글로빈 유사체에서 더 빠르게 축적됨)에 해당한다는 사실을 반영한다. 사이트 패턴 AAG를 고려할 경우 클라인 그룹 비트 쌍의 두 번째 요소는 이진 패턴 0000, 첫 번째 요소는 0011이 될 것이다. 이 경우 첫 번째 원소에 기초한 이진 패턴은 색인 3에 해당한다(0열의 3행, 표에 별표 1개로 표시). 사이트 패턴 GGAA, CCTT 및 TTCC는 정확히 동일한 방식으로 인코딩된다. 부지 패턴 AACT는 두 번째 요소에 기반한 이진 패턴 0011과 첫 번째 요소에 기반한 0001로 인코딩된다. 이것은 첫 번째 요소에 대한 지수 1과 두 번째 요소에 대한 지수 3으로 인코딩된다. 두 번째 클라인 그룹 비트 쌍에 기반한 지수는 8에 곱하여 컬럼 인덱스를 산출한다(이 경우 컬럼 24가 된다). AACT 사이트 패턴 카운트를 포함할 셀은 두 개의 별표로 표시되지만, 시퀀스 정렬에 AACT 사이트 패턴이 없음을 나타낸다(lik).ewise, CCAG, GGTC, TTGA 사이트 패턴은 동일한 방식으로 인코딩될 수 없음).

기타 응용 프로그램

Hadamard 변환은 JPEG XR, MPEG-4 AVC와 같은 많은 신호 처리 및 데이터 압축 알고리즘뿐만 아니라 데이터 암호화에도 사용된다. 비디오 압축 어플리케이션에서, 그것은 보통 절대 변환 차이의 합계의 형태로 사용된다. 양자컴퓨팅에서 그로버 알고리즘과 쇼어의 알고리즘에서도 결정적인 부분이다. Hadamard 변환은 NMR, 질량 분광학, 결정학 등의 실험 기법에도 적용된다. 그것은 의사 무작위 매트릭스 회전을 얻기 위해 지역성 민감 해싱의 일부 버전에서 추가로 사용된다.

참고 항목

외부 링크

Ritter, Terry (August 1996). "Walsh–Hadamard Transforms: A Literature Survey".
Akansu, A.N.; Poluri, R. (July 2007). "Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications" (PDF). IEEE Transactions on Signal Processing. 55 (7): 3800–6. doi:10.1109/TSP.2007.894229. S2CID 6830633.
이산형 분수 Hadamard 변환을 이용한 Pan, Jeng-shang 데이터 암호화 방법(2009년 5월 28일)
라코비치, 닥터 파웰 월시-하다마드 변환 및 금융 수익 시리즈 랜덤성 테스트(2015년 4월 7일)
Beddard, Godfrey; Yorke, Briony A. (January 2011). "Pump-probe Spectroscopy using Hadamard Transforms" (PDF).
Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (September 2014). "Time-resolved crystallography using the Hadamard transform". Nature Methods. 11 (11): 1131–1134. doi:10.1038/nmeth.3139. PMC 4216935. PMID 25282611.

참조

^ Cite 저널의 그림 1 비교 요구(도움말)
^ ^a ^b Kunz, H.O. (1979). "On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms". IEEE Transactions on Computers. 28 (3): 267–8. doi:10.1109/TC.1979.1675334. S2CID 206621901.
^ 부울 지도의 푸리에 분석 - 자습서 -, 페이지 12-13
^ 강의 5: 기본 양자 알고리즘, Rajat Mital, 페이지 4–5
^ Hendy, Michael D.; Penny, David (December 1989). "A Framework for the Quantitative Study of Evolutionary Trees". Systematic Zoology. 38 (4): 297. doi:10.2307/2992396. JSTOR 2992396.
^ Hendy, Michael D.; Penny, David (January 1993). "Spectral analysis of phylogenetic data". Journal of Classification. 10 (1): 5–24. doi:10.1007/BF02638451. ISSN 0176-4268. S2CID 122466038.
^ Székeley, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993년) 진화 나무를 위한 푸리에 반전 공식. 응용 수학 문자, 6(2), 13–16.
^ Felsenstein, Joseph (November 1981). "Evolutionary trees from DNA sequences: A maximum likelihood approach". Journal of Molecular Evolution. 17 (6): 368–376. doi:10.1007/BF01734359. ISSN 0022-2844. PMID 7288891. S2CID 8024924.
^ Stamatakis, Alexandros (2019), Warnow, Tandy (ed.), "A Review of Approaches for Optimizing Phylogenetic Likelihood Calculations", Bioinformatics and Phylogenetics, Computational Biology, Cham: Springer International Publishing, 29, pp. 1–19, doi:10.1007/978-3-030-10837-3_1, ISBN 978-3-030-10836-6, retrieved 2020-10-10
^ Chor, Benny; Hendy, Michael D.; Holland, Barbara R.; Penny, David (2000-10-01). "Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach". Molecular Biology and Evolution. 17 (10): 1529–1541. doi:10.1093/oxfordjournals.molbev.a026252. ISSN 1537-1719. PMID 11018159.
^ Matsen, Frederick A.; Steel, Mike (2007-10-01). Ané, Cécile; Sullivan, Jack (eds.). "Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology". Systematic Biology. 56 (5): 767–775. doi:10.1080/10635150701627304. ISSN 1076-836X. PMID 17886146.
^ Waddell, Peter J; Steel, M.A (December 1997). "General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites". Molecular Phylogenetics and Evolution. 8 (3): 398–414. doi:10.1006/mpev.1997.0452. PMID 9417897.
^ Steel, M. A.; Hendy, M. D.; Penny, D. (1993-12-01). "Parsimony Can Be Consistent!". Systematic Biology. 42 (4): 581–587. doi:10.1093/sysbio/42.4.581. ISSN 1063-5157.
^ ^a ^b ^c Hendy, M. D.; Penny, D.; Steel, M. A. (1994-04-12). "A discrete Fourier analysis for evolutionary trees". Proceedings of the National Academy of Sciences. 91 (8): 3339–3343. doi:10.1073/pnas.91.8.3339. ISSN 0027-8424. PMC 43572. PMID 8159749.
^ Miyamoto, M. M.; Koop, B. F.; Slightom, J. L.; Goodman, M.; Tennant, M. R. (1988-10-01). "Molecular systematics of higher primates: genealogical relations and classification". Proceedings of the National Academy of Sciences. 85 (20): 7627–7631. doi:10.1073/pnas.85.20.7627. ISSN 0027-8424. PMC 282245. PMID 3174657.

[1] Cite 저널의 그림 1 비교 요구(도움말)

[kunz-2] Kunz, H.O. (1979). "On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms". IEEE Transactions on Computers. 28 (3): 267–8. doi:10.1109/TC.1979.1675334. S2CID 206621901.

[3] 부울 지도의 푸리에 분석 - 자습서 -, 페이지 12-13

[4] 강의 5: 기본 양자 알고리즘, Rajat Mital, 페이지 4–5

[5] Hendy, Michael D.; Penny, David (December 1989). "A Framework for the Quantitative Study of Evolutionary Trees". Systematic Zoology. 38 (4): 297. doi:10.2307/2992396. JSTOR 2992396.

[6] Hendy, Michael D.; Penny, David (January 1993). "Spectral analysis of phylogenetic data". Journal of Classification. 10 (1): 5–24. doi:10.1007/BF02638451. ISSN 0176-4268. S2CID 122466038.

[7] Székeley, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993년) 진화 나무를 위한 푸리에 반전 공식. 응용 수학 문자, 6(2), 13–16.

[8] Felsenstein, Joseph (November 1981). "Evolutionary trees from DNA sequences: A maximum likelihood approach". Journal of Molecular Evolution. 17 (6): 368–376. doi:10.1007/BF01734359. ISSN 0022-2844. PMID 7288891. S2CID 8024924.

[9] Stamatakis, Alexandros (2019), Warnow, Tandy (ed.), "A Review of Approaches for Optimizing Phylogenetic Likelihood Calculations", Bioinformatics and Phylogenetics, Computational Biology, Cham: Springer International Publishing, 29, pp. 1–19, doi:10.1007/978-3-030-10837-3_1, ISBN 978-3-030-10836-6, retrieved 2020-10-10

[10] Chor, Benny; Hendy, Michael D.; Holland, Barbara R.; Penny, David (2000-10-01). "Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach". Molecular Biology and Evolution. 17 (10): 1529–1541. doi:10.1093/oxfordjournals.molbev.a026252. ISSN 1537-1719. PMID 11018159.

[11] Matsen, Frederick A.; Steel, Mike (2007-10-01). Ané, Cécile; Sullivan, Jack (eds.). "Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology". Systematic Biology. 56 (5): 767–775. doi:10.1080/10635150701627304. ISSN 1076-836X. PMID 17886146.

[12] Waddell, Peter J; Steel, M.A (December 1997). "General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites". Molecular Phylogenetics and Evolution. 8 (3): 398–414. doi:10.1006/mpev.1997.0452. PMID 9417897.

[13] Steel, M. A.; Hendy, M. D.; Penny, D. (1993-12-01). "Parsimony Can Be Consistent!". Systematic Biology. 42 (4): 581–587. doi:10.1093/sysbio/42.4.581. ISSN 1063-5157.

[:0-14] Hendy, M. D.; Penny, D.; Steel, M. A. (1994-04-12). "A discrete Fourier analysis for evolutionary trees". Proceedings of the National Academy of Sciences. 91 (8): 3339–3343. doi:10.1073/pnas.91.8.3339. ISSN 0027-8424. PMC 43572. PMID 8159749.

[15] Miyamoto, M. M.; Koop, B. F.; Slightom, J. L.; Goodman, M.; Tennant, M. R. (1988-10-01). "Molecular systematics of higher primates: genealogical relations and classification". Proceedings of the National Academy of Sciences. 85 (20): 7627–7631. doi:10.1073/pnas.85.20.7627. ISSN 0027-8424. PMC 282245. PMID 3174657.

[1]

[2]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Search