0. Talktorials
모든 study 는 TeachOpenCADD 를 바탕으로 구성하였습니다.
T005 · Compound clustering — TeachOpenCADD 0 documentation
Github:
1. Theory
1-1. Introduction to clustering and Jarvis-Patrick algorithm
Clustering 은 무엇일까요? 머신러닝 공부하다보면 비지도 학습의 예시로 clustering 이라는 단어 많이 듣게 됩니다. clustering 의 개념은 같은 그룹(cluster)에 속한 객체들이 더 유사하고, 다른 그룹(cluster)에 속한 객체들보다 서로 더 비슷한 특성을 가지도록 객체들을 묶는 작업입니다.
Compound clustering 도 화학적, 구조적으로 비슷한 compound 끼리 묶고 cluster 마다 어떤 특성을 가지는 지 분석할 때 사용됩니다.
보통의 clustering 은 neighboring points 간의 유사도를 기반으로 clustering 을 합니다.
cheminformatics 에서는 compound 들이 molecular fingerprints 로 encoding 되고, similarity 는 Tanimoto similarity 로 설명할 수 있습니다. (T004 study 내용)
예전부터 많이 사용되는 알고리즘은 Jarvis-Patrick clustering 입니다.
Paper title:
Jarvis, Raymond Austin, and Edward A. Patrick. "Clustering using a similarity measure based on shared near neighbors." IEEE Transactions on computers 100.11 (1973): 1025-1034.
Jarvis-Patrick clustering 은 두 개의 파라미터 K와 K_min 으로 정의됩니다.
각 분자에 대해 K개의 가장 가까운 neighbors 을 계산하고, 두 분자가
- 서로가 가장 가까운 이웃 목록에 포함되어 있어야 한다.
- 서로 K개의 가장 가까운 이웃 중 최소 K_min 개 이상을 공유하고 있어야 한다.
이 두 조건을 모두 만족할 경우에 cluster 로 묶입니다.
Jarvis-Patrick clustering 은 deterministic 하고, 대용량 데이터도 빠르게 처리한다는 특징이 있습니다. deterministic 하다는 것은 돌릴 때마다 결과가 같다는 뜻입니다. 단점은 cluster 들이 너무 커질 수 있고 heterogeneous clusters 가 섞일 수 있습니다. (이게 왜 이 cluster 에 들어가지..? 라는 생각이 드는 분자가 섞일 수도 있다는 말) 그래서 Butina clustering 과 이런 부분이 비교되기도 합니다.
clustering 에 관한 더 구체적인 자료: 2.3. Clustering — scikit-learn 1.6.1 documentation
1-2. Detailed explanation of Butina clustering
Butina clustering 도 자주 사용되는 알고리즘입니다. homogeneous clusters 으로 나누기 위해 개발되었습니다.
핵심 아이디어:
각 cluster 내에 cluster centroid 가 존재하고, 이 중심 분자와 군집 내 모든 분자들 간의 유사도가 특정 cut-off 이상이 되도록 cluster 를 형성하는 것입니다.
Paper title:
Butina, Darko. "Unsupervised data base clustering based on daylight's fingerprint and Tanimoto similarity: A fast and automated way to cluster small and large data sets." Journal of Chemical Information and Computer Sciences 39.4 (1999): 747-750.
알고리즘을 단계적으로 설명하겠습니다.
1. Data preparation and compound encoding
input 화합물 (예: SMILES) 을 molecular fingerprints (예: RDK5) 로 변환합니다.
(Fingerprint 는 분자의 구조적 특징을 bit-vector 형태로 표현합니다.)
2. Tanimoto similarity (or distance) matrix
분자 간의 유사도는 Tanimoto 계수를 통해 계산됩니다. 이때, 분자들 간의 similarity matrix (행렬의 크기는 n x n, n 은 분자수, 중복 계산 방지 목적으로 upper triangle matrix 만 사용) 또는 distance matrix (1 - similarity) 를 생성할 수 있습니다.
3. Clustering molecules: Centroids and exclusion spheres
Identification of potential cluster centroids
각 분자에 대해 Tanimoto distance 가 지정된 cut-off 보다 작은 모든 분자를 이웃으로 정합니다. neighbors 수를 기준으로 분자들을 내림차순 정렬해서 가장 많은 이웃을 가진 분자들이 cluster centroid 후보로 오게 되는데, 그렇기 때문에 cluster centroid 는 해당 cluster 내에서 가장 많은 neighbors 를 가진 분자입니다.
Clustering based on the exclusion spheres
Tanimoto 유사도 cut-off 이상인 분자들은 해당 중심 분자의 cluster 에 포함된다고 하였습니다. 한 번 cluster 의 멤버로 들어가게 되면 다른 cluster 의 중심이 될 수도 없고, 다른 cluster 의 멤버가 될 수 없습니다. clustering 이 끝날 때까지 cluster 에 속하지 못한 분자들은 singletons 으로 간주됩니다. (이웃 분자가 있음에도 singletons 일 수가 있는데, 그 이웃들이 다른 cluster 에 속해 있으면 이런 경우가 발생합니다.)
그림을 보면 금방 이해가 됩니다!
먼저, 각 분자의 fingerprint 를 계산합니다.
Tanimoto similarity 를 계산하는데, 여기서 cut-off 는 0.7 입니다. (threshold = cut-off, 임계점)
유사도 계산이 끝나면 0.7 이상의 유사도를 가진 분자만 이웃 분자로 취급합니다. 그리고 각 분자의 이웃 분자들의 개수를 세고 이웃 분자 수가 많은 분자들을 내림차순 정렬합니다. (그림을 보시면 분홍네모, 연두세모, 노랑네모 가 이웃 분자수가 5개라 정렬 후 상위에 위치해 있는 것을 알 수 있습니다.)
이제 본격적인 clustering 을 분홍 네모를 기준으로 시작합니다. 분홍 네모와 이웃하는 분자는 주황세모, 파랑네모, 하늘세모, 연두세모, 노랑네모 가 있습니다. 이 분자들로 먼저 cluster 를 구성하고
다음 분자인 초록 동그라미를 기준으로 cluster 를 기준으로 clustering 합니다.
-
Why? 분홍네모 다음엔 연두세모가 상위에 있는 분자인데 왜 연두세모를 기준으로 clustering 하지 않는 것일까요?
이것이 앞서 설명한 "Clustering based on the exclusion spheres" 입니다.
: 한 번 cluster 의 멤버로 들어가게 되면 다른 cluster 의 중심이 될 수도 없고, 다른 cluster 의 멤버가 될 수 없습니다.
-
그래서 분홍네모의 cluster 에 들어가게 된 연두세모, 노랑네모는 중심원자가 되지 않고 초록 동그라미를 기준으로 cluster 를 구성하는 것입니다.
결국 cluster 2개가 형성되고 clustering 은 끝나게 됩니다.
1-3. Picking diverse compounds
저희가 만약 virtual screening 을 하고 hit 으로 추정되는 분자를 실험적으로 확인하는 연구를 하려는데 실제 실험을 전부 다 하지 못하고 몇 개의 화합물만 실험으로 확인할 수 있다면 어떻게 해야 할까요? 최대한 screening 결과의 분자들을 꼼꼼히 분석해야 합니다. 또한, 최대한 다양한 구조의 화합물을 실험해보면 좋을 것 같습니다.
이럴 때 clustering 을 사용해서 cluster 의 대표 분자를 뽑는 것도 가능하고, cluster 내의 분자들의 미세한 구조 차이를 알고 싶다면 하나의 cluster 에 집중해서 분석해보는 것도 연구 방법 중 하나가 될 수 있습니다.
2. Practical
- 실습과는 다른 코드
- fingerprint → clustering → cluster MCS → 대표 분자 시각화
이 코드에서는 similarity cut off 가 아니라 distance 를 사용하였으므로 1- similarity 입니다. 따라서 값을 낮출수록 (예: 0.3) 더 유사한 분자가 cluster 로 묶이고 값을 높이면 (예: 0.7) 덜 유사해도 같은 cluster 로 묶이기 때문에 많은 분자가 한 cluster 에 속하게 됩니다. Similarity cut-off 를 사용하게 되면 이것과는 반대로 적용되겠죠.
import pandas as pd
from rdkit import Chem
from rdkit.Chem import AllChem, Draw
from rdkit.ML.Cluster import Butina
from rdkit.DataStructs.cDataStructs import TanimotoSimilarity
from rdkit.Chem import rdFMCS
from IPython.display import display
import matplotlib.pyplot as plt
# 1.데이터 불러오기
df = pd.read_csv("score_1_filtered.csv")
# 2.SMILES → Mol 변환
df = df.dropna(subset=["smile", "id"])
smiles_list = df["smile"].astype(str).tolist()
mols = [Chem.MolFromSmiles(s) for s in smiles_list]
ids = df["id"].astype(str).tolist()
# 유효한 Mol만 유지
mol_id_pairs = [(m, i) for m, i in zip(mols, ids) if m is not None]
mols = [m for m, _ in mol_id_pairs]
ids = [i for _, i in mol_id_pairs]
# 3.Fingerprint 생성
fps = [AllChem.GetMorganFingerprintAsBitVect(m, 2, 1024) for m in mols]
# 4.거리 계산
dists = []
for i in range(1, len(fps)):
dists.extend([1 - TanimotoSimilarity(fps[i], fps[j]) for j in range(i)])
# 5.Butina 클러스터링
clusters = Butina.ClusterData(dists, len(fps), 0.5, isDistData=True)
# 여기서 0.5 는 distance 이기 때문에 1 - similarity 로 계산됩니다.
# 즉, 값이 0에 가까울수록 유사하다는 뜻
print(f"클러스터 수: {len(clusters)}")
# 6.클러스터 대표 분자 + MCS 하이라이트
highlighted_mols = []
highlight_atom_lists = []
legends = []
for idx, cluster in enumerate(clusters):
cluster_mols = [mols[i] for i in cluster]
cluster_ids = [ids[i] for i in cluster]
rep_mol = cluster_mols[0]
rep_id = cluster_ids[0]
match_atoms = ()
try:
if len(cluster_mols) >= 2:
mcs_result = rdFMCS.FindMCS(cluster_mols, timeout=5)
patt = Chem.MolFromSmarts(mcs_result.smartsString)
match_atoms = rep_mol.GetSubstructMatch(patt)
except:
match_atoms = ()
rep_mol = Chem.Mol(rep_mol) # 복사
highlighted_mols.append(rep_mol)
highlight_atom_lists.append(list(match_atoms))
legends.append(f"Cluster {idx+1} | ID: {rep_id} | n={len(cluster)}")
# 7.시각화
img = Draw.MolsToGridImage(
highlighted_mols,
molsPerRow=3,
subImgSize=(1000, 1000),
legends=legends,
highlightAtomLists=highlight_atom_lists
)
display(img)
Reference
- Jarvis, Raymond Austin, and Edward A. Patrick. "Clustering using a similarity measure based on shared near neighbors." IEEE Transactions on computers 100.11 (1973): 1025-1034.
- https://docs.chemaxon.com/display/docs/jklustor_jarvis-patrick-clustering.md
- Butina, Darko. "Unsupervised data base clustering based on daylight's fingerprint and Tanimoto similarity: A fast and automated way to cluster small and large data sets." Journal of Chemical Information and Computer Sciences 39.4 (1999): 747-750.
- 2.3. Clustering — scikit-learn 1.6.1 documentation
- 현재 관련 분야를 공부하고 있는 전문가가 아닌 학생이기 때문에 틀린 내용이 있을 수 있습니다.
- 오타와 틀린 부분을 댓글로 알려주시면 수정하도록 하겠습니다.
'Drug study > TeachOpenCADD' 카테고리의 다른 글
| T007 · Ligand-based screening: machine learning (2) | 2025.05.13 |
|---|---|
| T006 · Maximum common substructure (0) | 2025.05.07 |
| T004 · Ligand-based screening: compound similarity (2) | 2025.04.16 |
| T003 · Molecular filtering: unwanted substructures (0) | 2025.04.08 |
| T002 · Molecular filtering: ADME and lead-likeness criteria (0) | 2025.04.07 |