Jabarkan Pencarian dari Basis data kimia

Kimiawan dapat mencari basis data dengan menggunakan bagian-bagian struktur, bagian dari nama IUPAC mereka dan juga berdasarkan pada batasan pada sifatnya. Basis data kimia sangat berbeda dengan basis data tujuan umum lainnya dalam dukungan mereka untuk pencarian sub-struktur. Jenis pencarian ini dicapai dengan mencari subgrafik isomorfisme (terkadang juga disebut monomorfisme) dan merupakan aplikasi teori graf yang banyak dipelajari. Algoritme untuk pencarian bersifat komputasi intensif, sering kali O (n3) atau O (n4) kali kompleksitas (di mana n adalah jumlah atom yang terlibat). Komponen pencarian yang intensif disebut atom-by-atom-searching (ABAS), di mana pemetaan pencarian substruktur atom dan ikatan dengan molekul target dicari. Pencarian ABAS biasanya menggunakan algoritme Ullman atau variasinya (mis. SMSD). Percepatan dicapai dengan amortisasi waktu, yaitu beberapa saat pada tugas pencarian disimpan dengan menggunakan informasi prakomputasi. Perhitungan awal ini biasanya melibatkan pembuatan bitstring yang mewakili ada tidaknya fragmen molekul. Dengan melihat fragmen yang ada dalam struktur pencarian, dimungkinkan untuk menghilangkan kebutuhan perbandingan ABAS dengan molekul target yang tidak memiliki fragmen yang ada dalam struktur pencarian. Penghapusan ini disebut skrining/ penyaringan (jangan dikelirukan dengan prosedur penyaringan yang digunakan dalam penemuan obat terlarang). Bit-string yang digunakan untuk aplikasi ini juga disebut kunci struktural. Kinerja tombol seperti itu tergantung pada pilihan fragmen yang digunakan untuk membangun kunci dan probabilitas kehadiran mereka dalam basis data molekul. Jenis kunci lainnya menggunakan hash-code berdasarkan fragmen yang diturunkan secara komputasi. Hal ini disebut 'sidik jari' meski istilahnya kadang-kadang digunakan secara sinonim dengan kunci struktural. Jumlah memori yang dibutuhkan untuk menyimpan kunci struktural dan sidik jari ini dapat dikurangi dengan 'lipat', yang dicapai dengan menggabungkan bagian-bagian kunci dengan menggunakan operasi bitwise dan dengan demikian mengurangi keseluruhan panjangnya.