Недавно я начал внедрять ряд решений на базе Redis для клиентов Datablend. Redis часто называют базой данных NoSQL от Swiss Army Knife и по праву заслуживает этого звания. По своей сути это хранилище ключей в памяти . Значения, которые назначаются ключам, могут быть «структурированы» с помощью строк, хэшей, списков, наборов и отсортированных наборов. Мощь этих простых структур данных в сочетании с интуитивно понятным API-интерфейсом делает Redis действительно мощным средством решения различных проблем, связанных с «большими данными». Чтобы проиллюстрировать это, я повторно реализовал свой поиск молекулярного сходства на основе MongoDB через Redis и его интегрированную поддержку Lua. Как всегда, полный исходный код можно найти наDatablend публичный репозиторий GitHub .
1. Redis «Отпечаток пальца» Модель данных
Молекулярное сходство относится к сходству с химическими соединений по отношению к их структурным и / или функциональным качествам. Вычисляя молекулярные сходства, Cheminformatics может помочь в разработке новых лекарств, просматривая большие базы данных для потенциально интересных химических соединений. Химическое сходство может быть определено посредством использования так называемых отпечатков пальцев (то есть линейных химических структур субструктуры определенной длины). Сходство между соединениями определяется путем расчета коэффициента Танимото . Это вычисление включает в себя вычисление пересечений между наборами отпечатков пальцев, эта операция изначально поддерживается Redis.
Наша модель данных Redis для хранения отпечатков пальцев требует трех различных структур данных:
- Для каждого соединения , идентифицируемого уникальным ключом , мы храним его набор отпечатков пальцев (где каждый отпечаток снова идентифицируется уникальным ключом).
- Для каждого отпечатка пальца , идентифицируемого уникальным ключом , мы храним набор соединений, содержащих этот отпечаток. Эти наборы отпечатков пальцев могут восприниматься как инвертированные индексы составных наборов, упомянутых выше.
- Для каждого отпечатка пальца мы храним его количество вхождений через специальную клавишу веса .
Отпечатки пальцев рассчитываются с использованием библиотеки jCompoundMapper . Библиотека Jedis (Java Redis Client) используется для сохранения структур данных, упомянутых выше. Трех простых атомарных операций (строки 30, 33 и 35) достаточно для создания как инвертированных индексов (составные-> отпечатки пальцев и отпечатки-> составные), так и приращения сопровождающих счетчиков .
RandomAccessMDLReader reader = new RandomAccessMDLReader(new File(...));
EncodingFingerprint fingerprinter = new Encoding2DMolprint();
// We will use a pipeline in order to speedup the persisting process
Pipeline p = jedis.pipelined();
// Iterate the compounds one by one
for (int i = 0; i < reader.getSize(); i++) {
// Retrieve the molecule and the fingerprints for this molecule
Molecule molecule = reader.getMol(i);
FeatureMap fingerprints = new FeatureMap(fingerprinter.getFingerprint(molecule));
// Retrieve some of the compound properties we want to use later on
String compound_cid = (String)molecule.getProperty("PUBCHEM_COMPOUND_CID");
// Iterate the fingerprints
for (IFeature fingerprint : fingerprints.getKeySet()) {
// Check whether we already encountered the feature and create accordingly (
String thefeaturestring = fingerprint.featureToString();
if (!fingerprintlist.contains(thefeaturestring)) {
fingerprintlist.add(thefeaturestring);
}
// Get the index of the fingerprint
int fingerprintindex = fingerprintlist.indexOf(thefeaturestring);
// Increment the weight of this fingerprint (number of occurences)
p.incr(fingerprintindex + ":w");
// Create the inverted indexes
// Add the fingerprint to the set of fingerprints of this compound
p.sadd((compound_cid + ":f"), fingerprintindex + "");
// Add the compound to the set of compounds of this fingerprint
p.sadd(fingerprintindex + ":c", compound_cid + "");
}
// Sync the changes
p.sync();
}
2. Поиск похожих химических соединений
Для получения соединений, которые удовлетворяют определенному коэффициенту Танимото, мы повторно используем те же принципы, которые изложены в моей первоначальной статье MongoDB . Количество обращений к хранилищу данных Redis сводится к минимуму за счет реализации алгоритма с помощью встроенной поддержки сценариев Lua . Мы начнем с получения количества отпечатков пальцев конкретного входного соединения. Основываясь на этой мощности, мы вычисляем интересующие нас отпечатки пальцев (т.е. минимальный набор отпечатков пальцев, который приводит нас к соединениям, способным удовлетворить коэффициент Танимото). Для этого нам нужно идентифицировать подмножество составных отпечатков пальцев, которые встречаются реже всего во всем наборе данных. Redis позволяет нам выполнить этот запрос с помощью одного вида-command; он принимает составной ключ в качестве ввода и сортирует содержащиеся в нем отпечатки пальцев, используя значение внешних клавиш веса отпечатков пальцев. Из этого отсортированного набора отпечатков пальцев мы отбираем верхние интересующие нас отпечатки пальцев . Какая мощная и элегантная команда!
Мы используем инвертированный индекс (фингерпринт-> соединения), чтобы идентифицировать те соединения, которые способны удовлетворить определенный входной коэффициент Танимото. Применение команды Redis union к вычисленному набору ключей отпечатков пальцев возвращает набор потенциальных соединений. После определения этого набора мы вычисляем сходство, используя команду Redis intersect . Только соединения, которые удовлетворяют ограничению Tanimoto, возвращаются.
-- Retrieve the input paramters
local inputCompound = ARGV[1];
local similarity = ARGV[2];
-- Get the number of fingerprints of the input compound
local countToFind = redis.call('scard', inputCompound .. ':f');
-- Calculate the max, min and number of fingerprints to consider
local maxFingerprints = math.floor(countToFind / similarity);
local minFingerprints = math.floor(countToFind * similarity);
local numberOfFingerprintsToconsider = math.floor(countToFind - minFingerprints);
-- Retrieve the fingerprints of interest by subselecting out of the sorted list of fingerprints based upon the number of occurences
local fingerprintsOfInterest = redis.call('sort', inputCompound .. ':f', 'by', '*:w', 'limit', 0, numberOfFingerprintsToconsider + 1);
-- Create the set of all fingerprints we are interested in (creating the redis keys along the way)
local fingerprintKeys = {};
for index = 1, #fingerprintsOfInterest do
table.insert(fingerprintKeys, fingerprintsOfInterest[index] .. ':c');
end
-- Retreive the set of possible matching compounds by taking the union of the fingerprint -> compound indexes
local possibleCompounds = redis.call('sunion',unpack(fingerprintKeys));
-- Calculate the tanimoto coefficient for the list of possible matching compounds with the inputcompound
local results = {};
for index = 1, #possibleCompounds do
-- Check whether the count of fingerprints is within the predefined range
local count = redis.call('scard', possibleCompounds[index] .. ':f');
if count >= minFingerprints and count <= maxFingerprints then
-- Calculate the matching fingerprints by calculating the intersection
local intersectCount = redis.call('sinter', inputCompound .. ':f', possibleCompounds[index] .. ':f');
local tanimoto = #intersectCount / (count + countToFind - #intersectCount);
-- If sufficient similar, add it the set of results
if tanimoto >= tonumber(similarity) then
table.insert(results,possibleCompounds[index]); table.insert(results, '' .. tanimoto);
end
end
end
-- Return the results
return results;
3. Вывод
При хранении 25 000 соединений Redis требуется менее 20 мс для извлечения соединений, которые на 70% похожи на конкретное входное соединение. Snappier по сравнению с моей первоначальной реализацией MongoDB. Кроме того, Redis требуется менее 1 ГБ ОЗУ для поддержания живого индекса 460 000 соединений PubChem , у которых есть хотя бы один связанный анализ. Это позволяет ученому размещать локальный экземпляр хранилища составных данных, эффективно устраняя необходимость в отдельной (и дорогой) настройке составной базы данных.