A fast diagonalization algorithm to enable singular value decomposition of large matrices for efficient template matching

세포의 보이지 않는 퍼즐

거대하고 소용돌이치는 스노우 글로브 안에 숨겨진 아주 작고 특정한 장난감을 찾는다고 상상해 보세요. 이제 그 스노우 글로브가 살아있는 세포이고, 장난감은 단백질 분자이며, 눈송이는 수천 개의 다른 분자들이 뒤섞여 흐릿하게 뭉쳐 있는 혼돈 상태라고 상상해 보세요. 이것이 바로 초저온 전자 현미경(cryo-EM)이라는 강력한 현미경을 사용하는 과학자들이 매일 마주하는 도전입니다. 이 기술은 세포를 매우 빠르게 얼려 그 작은 부분들이 얼음 속에 갇히게 함으로써 우리가 그것들을 볼 수 있게 해줍니다. 하지만 세포는 너무나 복잡하고 이미지는 매우 거칠기 때문에, 특정 단백질을 찾는 것은 마치 눈보라 속에서 특정한 눈송이 하나를 찾아내는 것과 같습니다.

이를 해결하기 위해 과학자들은 "템플릿 매칭(template matching)"이라 불리는 기술을 사용합니다. 이것은 고도의 기술이 적용된 "월리를 찾아라" 게임과 같습니다. 다만 만화 캐릭터 대신 3차원 분자를 찾는 것입니다. 여러분은 컴퓨터로 생성된 완벽한 분자 모델(템플릿)을 가져와서, 이를 흐릿한 현미경 이미지 위로 미끄러지듯 움직이며 모든 지점과 각도를 확인하여 모델이 일치하는지 검사합니다. 문제는 분자가 회전하거나 기울어질 수 있는 방법이 너무 많아서, 단 하나의 이미지를 위해서도 2,000만 개 이상의 서로 다른 위치를 확인해야 한다는 점입니다. 세포 내의 모든 단백질에 대해 이 작업을 수행하는 데는 엄청난 컴퓨터 성능이 필요하며, 이는 대규모로 수행하기가 사실상 불가능합니다. 이는 마치 스마트 검색 엔진을 사용하는 대신, 도서관의 모든 책을 한 페이지씩 일일이 확인하며 읽으려는 것과 같습니다.

마법 같은 기술: 탐색의 접기

이 논문은 그 탐색 속도를 높여 산더 같은 업무를 아주 작은 언덕으로 만드는 영리한 새로운 방법을 소개합니다. 저자인 UC 버클리의 연구진은 이 방대한 "만약의 경우(what-ifs)" 목록(2,0{0}만 개의 위치)에 "대칭성"이라는 숨겨진 비밀이 있다는 것을 깨달았습니다.

피자 반죽을 공중에서 돌리고 있는 모습을 상상해 보세요. 반죽을 아무리 회전시켜도 반죽 자체의 모양은 변하지 않고 그저 돌아간 것처럼 보일 뿐입니다. 이러한 현미경 이미지의 세계에서도 단백질을 찾는 데 사용되는 수학적 원리는 동일하게 작동합니다. 이미지를 회전시키면 수학적 결과도 회전하지만, 문제의 핵심적인 "형태"는 그대로 유지됩니다. 저자들은 이러한 회전 대칭성 덕분에 2,000만 개의 위치를 일일이 확인할 필요가 없다는 점을 깨달았습니다. 대신, 수학적 지름길을 사용하여 문제를 "접을(fold)" 수 있었습니다.

그들은 마치 마법의 디코더 링처럼 작동하는 빠른 알고리즘을 개발했습니다. 이 알고리즘은 거대하고 복잡한 퍼즐을 한꺼번에 해결하려고 노력하는 대신, 이미지가 회전하는 방식에 따라 문제를 더 작고 관리 가능한 덩어리로 나눕니다. 즉, 거대하고 다루기 힘든 행렬(모든 가능성을 나타내는 거대한 숫자 격자)을 훨씬 작고 조직화된 조각들로 변환합니다. 이 회전 대칭성을 활용함으로써, 그들은 전체의 거대한 격자를 직접 구축하지 않고도 가장 중요한 패턴(특이값 및 벡터라고 불리는 것)을 계산할 수 있습니다.

결과는 놀랍습니다. 테스트 결과, 이 새로운 방식은 오차를 극도로 낮게(단 0.01%) 유지하면서 데이터를 3,500배 압축할 수 있었습니다. 이를 체감하기 위해 설명하자면, 기존 방식이 세포 이미지에서 한 종류의 단백질을 찾는 데 4시간이 걸렸다면, 이 새로운 방식은 그보다 훨씬 짧은 시간 안에 그 일을 끝낼 수 있습니다. 구체적인 테스트에서, 이 새로운 알고로리즘은 발견된 각각의 특징당 205배 더 빠르게 작동했으며, 기존 방식이 찾을 수 있었던 것보다 22.5배 더 많은 특징을 포착해 냈습니다.

저자들은 또한 이 기술이 대규모로도 작동함을 보여주었습니다. 그들은 단백질이 보일 수 있는 모든 방식을 매우 높은 해상도(2 옹스트롬)로 다루는 템플릿 매칭 행렬을 단 14분 만에 분해해 냈습니다. 이는 이전에는 시도하기에 너무 비용이 많이 들고 느린 작업이었습니다. 논문은 전체 규모의 행렬을 표준 컴퓨터 도구로 직접 해결하는 것은 여전히 어렵다고 언급하지만, 이 새로운 "대칭성 활용" 방식은 이를 실현 가능하게 만듭니다. 이는 단순히 속도를 높이는 것이 아니라, 우리 세포 속의 수많은 단백질을 찾아낼 수 있는 문을 열어줌으로써 생명이 분자 수준에서 어떻게 작동하는지에 대한 완전한 지도를 그릴 수 있게 도와줍니다. 저자들은 이것이 컴퓨터가 광범위한 일치를 빠르게 스캔한 다음 세부적인 확인을 위해 줌인(zoom-in)하는 "다중 정밀도(multi-precision)" 탐색으로 이어져, 세포 기계 장치에 대한 연구를 그 어느 때보다 빠르고 포괄적으로 만들 수 있을 것이라고 제안합니다.