Библиотека полнотекстового поиска Lucene предоставляет возможность организовать поиск по текстовым документам. Существуют так же средства, с помощью которых можно организовать поиск «похожих» химических структур, например, OpenBabel. Иногда может возникнуть потребность объединить эти два вида поиска в единой «канве». Например, если нужно создать систему, которая может отвечать на такие запросы: найти вещество, в текстовом описании которого есть слово «аминокислота», структурно похожее на индол (ожидается, что мы найдём аминокислоту триптофан). В этой статье описано решение данной задачи на основе полнотекстового движка Lucene.
Как известно, в основе полнотекстового поиска лежит построение инвертированного индекса. Текст документов разбивается на отдельные слова, для каждого из которых строится список документов, в которых встречается слово. Обычно кроме списка документов для данного слова, индекс содержит позиции слова в каждом документе.
Поиск похожих молекул в базах данных может быть основан на «молекулярных отпечатках». Часто «молекулярный отпечаток» представляет собой битовую строку, в которой каждому биту соответствует присутствие определённого свойства или структурного фрагмента. В роли меры близости используется коэффициент Танимото (частный случай коэффициента Жаккара).
В качестве простого примера молекулярного отпечатка, рассмотрим такой: Предположим, что мы хотим получить молекулярный отпечаток длинны n. Структура нарезается на одномерные цепочки атомов длинной не более чем k. К каждой полученной цепочке применяется hash-функция, которая сопоставляет цепочке число от 0 до n-1. Это число определяет номер бита, который будет выставлен в 1 в отпечатке.
Для таких манипуляций с химическими структурами можно использовать java-библиотеку Chemistry Development Kit (далее просто CDK). CDK распространяется под лицензией LGPL и содержит java-классы для представления структур, расчёта нескольких типов «молекулярных отпечатков», поддерживает множество химических форматов файлов. Например, нарезка молекулы на фрагменты может быть реализована так:
Описанный «молекулярный отпечаток» вычисляется с помощью класса CDK org.openscience.cdk.fingerprint.Fingerprinter.
Для того, чтобы использовать Lucene для поиска структур мы переформулируем поиск структур по отпечаткам в своего рода «поиск слов». Структура, как и в описанном выше методе построения отпечатка, нарезается на короткие одномерные цепочки, которые и будут аналогами слов в текстовом поиске. Таким образом, если мы предоставим системе другую структуру в качестве поискового запроса, то структура-запрос так же будет нарезана на цепочки, и результатом будут те структуры, в которых имеются такие же цепочки атомов. Механизм упорядочивания документов по релевантности будет стремиться выводить в первые позиции результатов те структуры, в которых с одной стороны имеют много совпадений, с другой стороны эти совпадения несильно «разбавлены». То есть логично ожидать, что на первом месте будет точно совпадающая структура (если, конечно, она есть среди проиндексированных), далее похожие структуры, отличающиеся одним атомом или группой, далее ещё сильнее отличающиеся структуры и.т.д.
Стоит заметить, что используемая в Lucene формула ранжирования по умолчанию (модель векторного пространства + TF-IDF) отличается от меры близости Танимото. Можно переопределить класс Similarity из Lucene под формулу коэффициента Танимото, но я не буду на этом останавливаться, тем более что формула по-умолчанию должна дать «качественно правильный» результат: структуры с большой долей пересечений фрагментов будут на первых местах в результате.
Этот подход к индексации и поиску молекул можно реализовать создав для Lucene специальный «химический токенизатор». Токенизатором (tokenizer) называется компонент Lucene, разбивающий текст на отдельные токены (чаще всего токенами являются слова). Я уже привёл выше основную логику работы этого токенизатора. Отличие будет заключаться в том, что в токенизаторе Lucene не надо получать сразу все токены в цикле. Вместо этого нужно реализовать метод Tokenizer.incrementToken(), который будет выдавать текстовые представления цепочек атомов по одной.
Существует несколько форматов представления молекул в виде текстовой строки. Пока что остановимся на поддержке только на одного из них — формата SMILES. CDK предоставляет парсер SMILES-строки (класс org.openscience.cdk.smiles.SmilesParser). Пользоватья им нетрудно:
Логика преобразования SMILES-представления молекул в структуру с целью дальнейшего разрезания её на токены-цепочки помещается в класс SmilesTokenizer.
Позволю себе опустить ряд малозначительных деталей, скажу только, что исходники выложены на GitHub. Перейду сразу к примеру использования этих классов для поиска структур. Предположим, что поисковые документы содержат три поля: name — имя химического соединения, description — текстовое описание, и поле smiles — информация о структуре молекулы.
Индексация документов может выглядеть примерно так (используется вспомогательный класс SmilesAnalyzer, который просто создаёт SmilesTokenizer):
Поиск же будет выглядеть примерно вот так:
Как известно, в основе полнотекстового поиска лежит построение инвертированного индекса. Текст документов разбивается на отдельные слова, для каждого из которых строится список документов, в которых встречается слово. Обычно кроме списка документов для данного слова, индекс содержит позиции слова в каждом документе.
Поиск похожих молекул в базах данных может быть основан на «молекулярных отпечатках». Часто «молекулярный отпечаток» представляет собой битовую строку, в которой каждому биту соответствует присутствие определённого свойства или структурного фрагмента. В роли меры близости используется коэффициент Танимото (частный случай коэффициента Жаккара).
В качестве простого примера молекулярного отпечатка, рассмотрим такой: Предположим, что мы хотим получить молекулярный отпечаток длинны n. Структура нарезается на одномерные цепочки атомов длинной не более чем k. К каждой полученной цепочке применяется hash-функция, которая сопоставляет цепочке число от 0 до n-1. Это число определяет номер бита, который будет выставлен в 1 в отпечатке.
Для таких манипуляций с химическими структурами можно использовать java-библиотеку Chemistry Development Kit (далее просто CDK). CDK распространяется под лицензией LGPL и содержит java-классы для представления структур, расчёта нескольких типов «молекулярных отпечатков», поддерживает множество химических форматов файлов. Например, нарезка молекулы на фрагменты может быть реализована так:
/Для представления химических структур в CDK используются реализации интерфейса IAtomContainer.
IAtomContainer structure;
...
for (IAtom startAtom : structure.atoms()) {
//нам будет интересен класс CDK org.openscience.cdk.graph.PathTools, который содержит метод getPathsOfLengthUpto, нарезающий структуру на одномерные цепочки.
List<List<IAtom>> paths = PathTools.getPathsOfLengthUpto(structure,
startAtom,
searchDepth);
//Далее делаем что-то с цепочкой атомов
...
}
Описанный «молекулярный отпечаток» вычисляется с помощью класса CDK org.openscience.cdk.fingerprint.Fingerprinter.
Для того, чтобы использовать Lucene для поиска структур мы переформулируем поиск структур по отпечаткам в своего рода «поиск слов». Структура, как и в описанном выше методе построения отпечатка, нарезается на короткие одномерные цепочки, которые и будут аналогами слов в текстовом поиске. Таким образом, если мы предоставим системе другую структуру в качестве поискового запроса, то структура-запрос так же будет нарезана на цепочки, и результатом будут те структуры, в которых имеются такие же цепочки атомов. Механизм упорядочивания документов по релевантности будет стремиться выводить в первые позиции результатов те структуры, в которых с одной стороны имеют много совпадений, с другой стороны эти совпадения несильно «разбавлены». То есть логично ожидать, что на первом месте будет точно совпадающая структура (если, конечно, она есть среди проиндексированных), далее похожие структуры, отличающиеся одним атомом или группой, далее ещё сильнее отличающиеся структуры и.т.д.
Стоит заметить, что используемая в Lucene формула ранжирования по умолчанию (модель векторного пространства + TF-IDF) отличается от меры близости Танимото. Можно переопределить класс Similarity из Lucene под формулу коэффициента Танимото, но я не буду на этом останавливаться, тем более что формула по-умолчанию должна дать «качественно правильный» результат: структуры с большой долей пересечений фрагментов будут на первых местах в результате.
Этот подход к индексации и поиску молекул можно реализовать создав для Lucene специальный «химический токенизатор». Токенизатором (tokenizer) называется компонент Lucene, разбивающий текст на отдельные токены (чаще всего токенами являются слова). Я уже привёл выше основную логику работы этого токенизатора. Отличие будет заключаться в том, что в токенизаторе Lucene не надо получать сразу все токены в цикле. Вместо этого нужно реализовать метод Tokenizer.incrementToken(), который будет выдавать текстовые представления цепочек атомов по одной.
Существует несколько форматов представления молекул в виде текстовой строки. Пока что остановимся на поддержке только на одного из них — формата SMILES. CDK предоставляет парсер SMILES-строки (класс org.openscience.cdk.smiles.SmilesParser). Пользоватья им нетрудно:
SmilesParser sp = new SmilesParser(DefaultChemObjectBuilder.getInstance());
String smiles = "OCC(O)C(O)C(O)C(O)CO"; //Sorbitol
IAtomContainer structure = sp.parseSmiles( smiles );
//Далее делаем что-то с полученной структурой
...
Логика преобразования SMILES-представления молекул в структуру с целью дальнейшего разрезания её на токены-цепочки помещается в класс SmilesTokenizer.
Позволю себе опустить ряд малозначительных деталей, скажу только, что исходники выложены на GitHub. Перейду сразу к примеру использования этих классов для поиска структур. Предположим, что поисковые документы содержат три поля: name — имя химического соединения, description — текстовое описание, и поле smiles — информация о структуре молекулы.
Индексация документов может выглядеть примерно так (используется вспомогательный класс SmilesAnalyzer, который просто создаёт SmilesTokenizer):
Map<String,Analyzer> analyzerPerField = new HashMap<String,Analyzer>();
analyzerPerField.put(SMILES_FIELD, new SmilesAnalyzer() );
PerFieldAnalyzerWrapper analyzerWrapper =
new PerFieldAnalyzerWrapper(new StandardAnalyzer(Version.LUCENE_40), analyzerPerField);
Document doc = new Document();
doc.add( new TextField( "name", "Acetic acid", Field.Store.YES ) );
doc.add( new TextField( "description", "Acetic acid is one of the simplest carboxylic acids. Liquid.", Field.Store.YES ) );
doc.add( new TextField( "smiles", "CC(O)=O", Field.Store.YES ) );
Directory directory = null;
IndexWriter indexWriter = null;
try {
directory = new RAMDirectory();
IndexWriterConfig config = new IndexWriterConfig(Version.LUCENE_40, analyzerWrapper );
indexWriter = new IndexWriter( directory, config);
indexWriter.addDocument(doc);
}
...
Поиск же будет выглядеть примерно вот так:
reader = IndexReader.open(directory );
IndexSearcher searcher = new IndexSearcher(reader);
String querystr = "smiles:CCC";
Query q = null;
q = new QueryParser(Version.LUCENE_40, FREE_TEXT_FIELD, getAnalyzer()).parse(querystr);
TopScoreDocCollector collector = TopScoreDocCollector.create(5, true);
searcher.search(q, collector);
ScoreDoc[] hits = collector.topDocs().scoreDocs;
//Дальше что-то делаем с результатами поиска в hits
...
