Радость алгоритмов и NoSQL: пример MongoDB

3. MongoDB datamodel

MongoDB — это так называемая документно-ориентированная база данных . При использовании ориентированных на документы баз данных вы в основном группируете все связанные данные в одном документе, а не нормализуете свои данные в различных таблицах РСУБД и используете объединения для последующего получения необходимой информации. В случае MongoDB документы хранятся с использованием BSON (двоичный JSON), а связанные документы хранятся в коллекциях . Давайте начнем с описания коллекции соединений, в которой хранится отдельный документ для каждого соединения. JSON-документ нашего C ₅₂ H ₈₇ N ₃ O ₁₃ Состав выглядит следующим образом:

{ 
    "compound_cid" : "46200001" , 
    "smiles" : "CCC1C(C(C(C(=NOCC=CCN2CCCCC2)C(CC(C(C(C(C(C(=O)O1)C)OC3CC(C(C(O3)C)O)(C)OC)C)OC4C(C(CC(O4)C)N(C)CC5=CC=CC=C5)O)(C)O)C)C)O)(C)O" ,
    "fingerprint_count" : 120 , 
    "fingerprints" : [ 
        "0[N]1[C O]2[C C C]" ,
        "0[N]1[C O]2[C C C]3[C C C C C]" ,
        "0[C]1[C C C]2[C C N O]3[C C C C O O]" ,
        "0[C]1[C C]2[C C C C O]3[C C N O]" ,
        "0[O]1[C]2[C O]3[C C C]" , 
        "0[C]1[C O O]2[C C C O]" , 
        "0[C]1[C C]2[C C]" , 
        "0[C]1[C]2[C]3[C O]" , 
        "0[C]1[C C N]2[C C C C O]3[C C C O]" ,
        ... ] , 
}

Для каждого соединения мы храним свое уникальное представление PubChem Id и SMILES . Кроме того, мы храним полный набор уникальных шаблонов отпечатков пальцев в виде массива строк . В качестве ярлыка эффективности мы также храним общее количество шаблонов отпечатков пальцев как отдельное свойство. Следовательно, это число не нужно вычислять во время выполнения во время запроса. Храня всю составную информацию в одном документе , запросы могут выполняться более эффективно. Это по сравнению с более традиционной моделью RDBMS, где требуется соединение для извлечения информации, хранящейся в отдельной таблице составных соединений и отпечатков пальцев .Драйвер Java для MongoDB позволяет действительно легко создать этот документ JSON для каждого соединения. После того, как мы извлекли молекулу через программу чтения файлов MDL, нужно просто создать необходимые объекты документа и вставить их в коллекцию соединений .

// Retrieve the molecule
Molecule molecule = ...;
FeatureMap fingerprints = new FeatureMap(fingerprinter.getFingerprint(molecule));

// Create the new document that will hold the compound
BasicDBObject compound = new BasicDBObject();

// Add the simple properties one by one to this compound object
compound.put(COMPOUNDCID_PROPERTY, molecule.getProperty("PUBCHEM_COMPOUND_CID"));
compound.put(SMILES_PROPERTY, molecule.getProperties().get("PUBCHEM_OPENEYE_CAN_SMILES"));
compound.put(FINGERPRINTCOUNT_PROPERTY, fingerprints.getSize());

// Iterate the fingerprints
ArrayList fingerprintstosave = new ArrayList();
for (IFeature fingerprint : fingerprints.getKeySet()) {
    fingerprintstosave.add(fingerprint.featureToString());
}

// Add the full fingerprint list to the compound document
compound.put(FINGERPRINTS_PROPERTY, fingerprintstosave.toArray());

// Compound document is created, insert it.
compoundsCollection.insert(compound);

Чтобы завершить нашу модель данных MongoDB, мы добавим коллекцию fingerprintscount . Обоснование этой коллекции будет объяснено в следующем разделе этой статьи. А пока, просто рассмотрите, что это коллекция, в которой хранится количество раз, когда определенный шаблон отпечатка пальца встречался при импорте составных данных. Приведенный ниже список показывает выдержку из коллекции отпечатков пальцев .

{ 
    "fingerprint" : "0[N]1[C O]2[C C C]",
    "count" : 472
}
{ 
    "fingerprint" : "0[N]1[C O]2[C C C]3[C C C C C]",
    "count" : 41
}
{
    "fingerprint" : "0[O]1[C]2[C O]3[C C C]",
    "count" : 1343
} 

Чтобы обновить эту коллекцию, мы используем оператор приращения MongoDB в сочетании с upsert . Таким образом, всякий раз, когда образец отпечатка пальца встречается в первый раз, для отпечатка пальца автоматически создается документ, и его счет добавляется 1. Если документ для этого образца отпечатка пальца уже существует, связанный с ним счет увеличивается на 1. Довольно просто!

// Retrieve the molecule
Molecule molecule = ...;
FeatureMap fingerprints = new FeatureMap(fingerprinter.getFingerprint(molecule));

// Iterate the fingerprints
for (IFeature fingerprint : fingerprints.getKeySet()) {

    // Create a +1 increment count for this fingerprint
    BasicDBObject countplusone = new BasicDBObject();
    countplusone.put(COUNT_PROPERTY,1);
    BasicDBObject increment = new BasicDBObject();
    increment.put("$inc", countplusone);

    // Create the fingerprint document itself
    BasicDBObject the_fingerprint = new BasicDBObject();
    the_fingerprint.put(FINGERPRINT_PROPERTY, fingerprint.featureToString());

    // Perform an upsert
    fingerprintCountsCollection.update(the_fingerprint,increment,true,false);
}

Для повышения производительности запросов нам нужно определить индексы для соответствующих свойств документа. Таким образом, созданные индексы B-Tree используются оптимизатором запросов MongoDB для быстрого поиска необходимых документов, вместо того, чтобы сканировать их все. Создать эти индексы очень просто, как показано ниже.

compoundsCollection.ensureIndex(new BasicDBObject().append(FINGERPRINTS_PROPERTY, 1));
compoundsCollection.ensureIndex(new BasicDBObject().append(FINGERPRINTCOUNT_PROPERTY, 1));

fingerprintCountsCollection.ensureIndex(new BasicDBObject().append(FINGERPRINT_PROPERTY, 1));

4. Запрос молекулярного сходства MongoDB

Пришло время собрать все это вместе. Представьте, что мы хотим найти все соединения, которые имеют коэффициент Танимото 0,8 для конкретного входного соединения. Поскольку скорость запросов MongoDB достаточно высока, мы можем попытаться перебором и вычислить коэффициент Tanimoto для каждого составного документа, который хранится в коллекции составов. Но давайте попробуем сделать это немного умнее. Глядя на уравнение коэффициента Танимото, мы уже можем значительно сузить пространство поиска. Представьте, что у нашего входного соединения ( A ) 40 уникальных шаблонов отпечатков пальцев. Давайте заполним некоторые параметры в уравнении Танимото:

Из этого уравнения мы можем вычесть минимальное и максимальное количество уникальных образцов отпечатков пальцев, которое должно иметь другое соединение, чтобы (в лучшем случае) удовлетворить уравнению:

Следовательно, соединение, с которым мы сравниваем, следует рассматривать, только если оно имеет от 32 до 50 уникальных образцов отпечатков пальцев. Принимая это во внимание в нашем поисковом запросе, мы можем значительно сузить пространство поиска. Но мы можем оптимизировать наш запрос немного дальше. Представьте, что мы будем запрашивать все документы, которые имеют по крайней мере 1 из 9 уникальных шаблонов отпечатков пальцев с входным соединением. Все документы, которые не являются частью набора результатов этого запроса, никогда не смогут достичь коэффициента Танимото, равного 0,8, так как максимум возможных оставшихся общих шаблонов отпечатков пальцев будет 31 , и

если бы мы заменили N _B на 31, чтобы максимизировать полученный коэффициент Танимото. Это 9-число можно получить, решив следующее уравнение:

Какие 9 шаблонов отпечатков входного соединения мы должны рассмотреть в этом запросе? Здравый смысл подсказывает нам выбрать 9 шаблонов отпечатков пальцев, для которых встречаемость в общей совокупной совокупности является наименьшей , поскольку это еще больше сузит наше пространство поиска. (Следовательно, необходимо, чтобы коллекция считываний отпечатков пальцев могла быстро получать счетчики для отдельных шаблонов отпечатков пальцев.) В приведенном ниже листинге кода показано, как получить счетчики для отдельных шаблонов. Использование MongoDB QueryBuilder мы создаем объект запроса , который, используя в -оператора, указывает , что документ из fingerprintscountколлекция должна быть возвращена только в том случае, если ее шаблон отпечатков пальцев является частью интересующих нас шаблонов отпечатков пальцев. Используя дополнительный оператор сортировки , мы получаем отдельные шаблоны отпечатков пальцев в порядке возрастания количества .

// Find all fingerprint count documents that have a fingerprint in the list
DBObject fingerprintcountquery =   
    QueryBuilder.start(FINGERPRINT_PROPERTY).in(fingerprintsToFind.toArray()).get();

// Sort the result on count
DBObject fingerprintcountsort = 
    QueryBuilder.start(COUNT_PROPERTY).is(1).get();

// Execute the query on the fingerprint counts collection
DBCursor fingerprintcounts = 
    fingerprintCountsCollection.find(fingerprintcountquery).sort(fingerprintcountsort);

Настало время для последнего шага, а именно для извлечения всех составных документов, которые могут удовлетворить коэффициент Танимото, например, 0,8. Для этого мы строим запрос, который извлекает все соединения, которые имеют хотя бы один шаблон, из подсписка шаблонов отпечатков пальцев, который мы вычислили на предыдущем шаге. Кроме того, должны быть возвращены только те соединения, у которых общее количество образцов отпечатков пальцев находится в пределах минимального и максимального диапазона. Хотя этот оптимизированный запрос резко сужает пространство поиска, нам все равно необходимо вычислить коэффициент Танимото, чтобы убедиться, что он имеет значение 0,8 или выше.

// Calculate the essential numbers
int maxnumberofcompoundfingerprints = (int) (fingerprintsToFind.size() / 0.8);
int minnumberofcompoundfingerprints = (int) (fingerprintsToFind.size() * 0.8);
int numberoffingerprintstoconsider = fingerprintsToFind.size() - minnumberofcompoundfingerprints + 1;

List fingerprintsToConsider = fingerprintsToFind.subList(0,numberoffingerprintstoconsider);

// Find all compounds that satisfy the specified conditions
DBObject compoundquery =   
    QueryBuilder.start(FINGERPRINTS_PROPERTY).in(fingerprintsToConsider)
                .and(FINGERPRINTCOUNT_PROPERTY).lessThanEquals(maxnumberofcompoundfingerprints)
                .and(FINGERPRINTCOUNT_PROPERTY).greaterThanEquals(minnumberofcompoundfingerprints)
                .get();

// Execute the query
DBCursor compounds = compoundsCollection.find(compoundquery);

// Let's process the found compounds locally
while(compounds.hasNext()) {

    DBObject compound = compounds.next();
    // Retrieve all fingerprints of the compound
    BasicDBList fingerprints = ((BasicDBList) compound.get(FINGERPRINTS_PROPERTY));
    // Calculate the intersection on the total list of fingerprints
    fingerprints.retainAll(fingerprintsToFind);

    int sharecount = fingerprints.size();
    int totalcount = (Integer)compound.get(FINGERPRINTCOUNT_PROPERTY);
    // Calculate the Tanimoto coefficient
    double tanimoto = (double) sharedcount / (totalcount + fingerprintsToFind.size() - sharedcount);
    
    // We still need to check whether the tanimoto is really >= the required similarity
    if (tanimoto >= 0.8) {
        System.out.println(compound.get(COMPOUNDCID_PROPERTY) + " " + (int)(tanimoto * 100) + "%");
    }

}

5. Вывод

Внедрение MongoDB позволяет легко просматривать базу данных о миллионе соединений за секунду. Однако требуемое время расчета в значительной степени зависит от целевого Танимото: целевой Танимото 0,6 приведет к значительно большему количеству результатов по сравнению с целевым Танимото 0,8. Используя функциональность объяснения MongoDB , можно заметить, что время запроса довольно мало по сравнению со временем, которое требуется для передачи данных в приложение Java и выполнения вычислений Tanimoto. В моей следующей статье я расскажу об использовании встроенной в MongoDB функциональности map-Reduce для сохранения локальных вычислений Tanimoto для составных данных и, следовательно, повышения общей производительности.