Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии

При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбр...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	1990
Автор:	Певзнер, П.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут молекулярної біології і генетики НАН України 1990
Назва видання:	Биополимеры и клетка
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/154122
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-154122
record_format	dspace
spelling	irk-123456789-1541222019-06-16T01:26:10Z Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии Певзнер, П.А. При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбраковать» последовательности с низким уровнем гомологии. В работе вводится понятие эффективности фильтрации и дается оценка эффективности некоторых фильтров, при этом показано, что в l-граммном анализе эффективность фильтрации связана с потенциальным расширением исходного 4-буквенного алфавита. При пошуку локальних гомологій (пошук гомологій у генетичних банках, вибір оптимальних олігонуклеотидних зондів і т. п.) виникає проблема його «пришвидчення». Квадратична трудомісткість алгоритмів динамічного програмування змушує вдаватися до методів фільтрації, що дозволяє швидко «відбракувати» послідовності з низьким рівнем гомології. У роботі вводиться поняття ефективності фільтрації і дається оцінка ефективності деяких фільтрів, при цьому показано, що в l-грамному аналізі ефективність фільтрації пов’язана з потенційним розширенням вихідного 4-літерного алфавіту. Upon searching local homologies in long sequences (homology search in nucleotide and amino acid sequences banks, selection of optimal oligonucleotide probes etc.) the necessity of a «rapid» homology search becomes acute. Quadratic complexity of (he dymanic programming algorithms (Needleman–Wunsch and Sellers type) forces the employment of filtration methods, that permits one to reject the sequences with a low homology level (among the filtration methods the 1–tuple analysis and the statistical method of Mironov–Alexandrov were used). But theoretical substantiations of such algorithms have not been made yet. The present work introduces the notion of filtration efficiency and the efficiency of several filters is given. It was shown that in the 1–tuple analysis the filtration efficiency is associated with the potential extension of the original four– letter alphabet. The formulas that allow choosing the filtration parameters are presented. 1990 Article Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос. 0233-7657 DOI: http://dx.doi.org/10.7124/bc.000299 http://dspace.nbuv.gov.ua/handle/123456789/154122 519.764 ru Биополимеры и клетка Інститут молекулярної біології і генетики НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбраковать» последовательности с низким уровнем гомологии. В работе вводится понятие эффективности фильтрации и дается оценка эффективности некоторых фильтров, при этом показано, что в l-граммном анализе эффективность фильтрации связана с потенциальным расширением исходного 4-буквенного алфавита.
format	Article
author	Певзнер, П.А.
spellingShingle	Певзнер, П.А. Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии Биополимеры и клетка
author_facet	Певзнер, П.А.
author_sort	Певзнер, П.А.
title	Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
title_short	Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
title_full	Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
title_fullStr	Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
title_full_unstemmed	Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
title_sort	эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
publisher	Інститут молекулярної біології і генетики НАН України
publishDate	1990
url	http://dspace.nbuv.gov.ua/handle/123456789/154122
citation_txt	Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос.
series	Биополимеры и клетка
work_keys_str_mv	AT pevznerpa éffektivnostʹfilʹtraciivstatističeskihalgoritmahbystrogopoiskagomologii
first_indexed	2025-07-14T05:39:50Z
last_indexed	2025-07-14T05:39:50Z
_version_	1837599650911092736
fulltext	УДК 519.764 П. А. Певзнер ЭФФЕКТИВНОСТЬЮ ФИЛЬТРАЦИИ В СТАТИСТИЧЕСКИХ АЛГОРИТМАХ БЫСТРОГО ПОИСКА ГОМОЛОГИИ При поиске локальных гомологии, (поиск гомологий в генетических банках, выбор оп- тимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поис- ка. Квадратичная трудоемкость алгоритмов динамического программирования застав- ляет прибегать к методам фильтрации, позволяющим быстро <готбраковать» последова- тельности с низким уровнем гомологии. В работе вводится понятие эффективности фильтрации и дается оценка эффективности некоторых фильтров, при этом показано, что в l-граммном анализе эффективность фильтрации связана с потенциальным расши- рением исходного 4-буквенного алфавита. Введение. Для определения гомологии между последовательностями Д Н К в настоящее время используются методы динамического програм- мирования типа алгоритмов Нидельмана — Вунша и Селлерса [1, 2]. Оценка трудоемкости таких алгоритмов — квадратичная, поэтому для поиска гомологий в случае длинных последовательностей приходится искать альтернативные подходы. Известны попытки решения задачи поиска гомологий в банках генетической информации на суперкомпью- терах [3—5], а также с использованием параллельных алгоритмов [6]. Перспективы значительного расширения баз данных нуклеотидных последовательностей, связанные с секвенированием генома человека, выдвигают задачу разработки методов «быстрого» поиска гомологий. В связи с тем, что попытки уменьшить вычислительную сложность алго- ритмов, основанных на динамическом программировании, пока не при- вели к значительному снижению трудоемкости [7—12], в ряде работ [13—22] были предложены методы фильтрации для поиска гомологий по банку нуклеотидных последовательностей (аналогичные подходы предложены в работах [23—26]). Возможность введения фильтрации связана с тем, что при поиске локальных гомологий в длинных последовательностях биологов, как правило, интересуют фрагменты с достаточно высоким пороговым уров- нем гомологии (или, иными словами, фрагменты, расстояние между которыми мало), а все другие фрагменты отбрасываются. В данной работе считается, что задано пороговое значение расстояния b0 между окнами и окна с расстоянием b > b0 отбрасываются. Конечно, для вы- явления окон с b > Ь0 можно ki-k2 раз применить какой-нибудь из алгоритмов глобального поиска гомологий (например, алгоритм Ни- дельмана— Вунша) с трудоемкостью п2 (ku k2 — длины анализируе- мых последовательностей, η — длина окна) и получить для каждой пары окон, начинающихся в позициях і и /, точные значения расстоя- ния b(i, j ) . Если при этом нас интересуют только позиции (i, j) с уров- нем расстояния b(i, j) <b0, составляющие, например, 0,01 % от числа всех пар (і, / ) , то 99,99 % работы проделывается впустую, так как информация о точном уровне гомологии при b(i, j) > b0 не нужна. Методы фильтрации позволяют отказаться от трудоемкого опреде- ления расстояния b(i, j) между всеми окнами путем введения легко вычисляемого фильтра /(г, / ) , принимающего два значения 0 и 1, при этом из f(i, /) = 1 следует, что b (i, j) > b0. С введением фильтра f про- цедура поиска гомологий становится двухступенчатой: на первом этапе (фильтрация) вычисляется функция f(i,j) (при этом пары окон, для С П. А. ПЕВЗНЕР, 1990 ISSN 02ЭЭ-7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1990. Т. 6. № б 7 которых f(i, j) = 1 исключаются из дальнейшего рассмотрения), а на втором проводится вычисление b(i, j) для пар (і, /) , удовлетворяющих условию f(i, j) = 0 . Эффективность фильтрации определяется долей от- брошенных пар (i,j). Если бы оказалось, что для фильтра f из /(£, / ) = 0 следует b(i, j) < Ь0, мы имели бы «идеальный» фильтр, однако ни /-граммный анализ, ни метод Миронова — Александрова [16] не пред- лагают «идеальных» фильтров. Возникает вопрос об эффективности фильтрации, который и рассматривается в настоящей работе. Приве- денный анализ может быть использован при разработке методов «быст- рого» поиска гомологий, построении dot-matrix и выборе оптимальных олигонуклеотидных зондов — необходимых составляющих современных пакетов программ анализа биополимеров. Э ф ф е к т и в н о с т ь ф и л ь т р а ц и и . В большинстве работ по быстрому поиску гомологий отсутствуют оценки скорости, специфичности и чувствительности алгорит- мов [27]. Впервые эмпирическое изучение этих характеристик, позволяющее выбрать параметры для быстрого поиска гомологий, проведено Лоуренсом и др. [27]. В настоя- щей работе вводится понятие эффективности фильтрации в методах быстрого поиска гомологий и приводятся аналитические формулы для ее вычисления. Полученные ре- зультаты позволяют, в частности, объяснить разные параметры, рекомедуемые [27] для поиска гомологий в нуклеотидных и аминокислотных последовательностях (про- граммы DNASEARCH и PEPSEARCH соответственно). Как в /-граммном анализе, так и в методе Миронова — Александрова, для постро- ения фильтров вводится отображение h множества /г-буквенных слов в Rm (принци- пиально другой подход предложен в [21, 22]). При этом т = А 1 в /-граммном анализе и т= (i-\-\) -A2 в методе Миронова — Александрова (і — параметр алгоритма, харак- теризующий максимальный размер «дырки» в рассматриваемых разнесенных динуклео- тидах; А — размерность алфавита). После введения отображения h сходство между словами 5 и Г можно, как и в [16], определить через евклидово расстояние между точками h(S) = (Sb-, Sm) и h(T) = ( t t m ) : 8 ISSN 023Э-7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1990. Т. G. № & Расстояние d(S, Τ) называют иногда статистическим расстоянием (в [28] анало- гичный подход использован при введении автокорреляционной функции последователь- ности), подчеркивая его отличие от обычно используемого при сравнении текстов рас- стояния b(S, Τ)—минимального числа элементарных операций (вставок, делеций и т. п.), необходимых для преобразования SBT. Если S и T — случайные слова, то d(S, 7') —случайная величина. Можно рассмот- реть функцию распределения d(S, Г), которая и будет характеризовать эффективность фильтрации. Действительно, если нас интересуют только пары слов с расстоянием ниже порогового, то можно ввести пороговое значение статистического расстояния do и определить фильтр по правилу Эффективность фильтрации можно характеризовать вероятностью Величина P{d(S, T)<C=d0} определяет долю случаев, для которых фильтрация не при- водит к отбраковке слов S и Т. В этих случаях для анализа вопроса об отбраковке слов S n T приходится использовать алгоритмы динамического программирования. Эф- фективность фильтрации можно характеризовать, как принято в статистике, в терминах стандартных отклонений, т. е. с помощью величины где M—математическое ожидание; D — дисперсия случайной величины d (SiT) (для1 малых значений d0 можно приближенно положить чать е0)· будем обозна- Ф и л ь т р а ц и я по с о с т а в у . Рассмотрим простейшую фильтрацию, когда в качестве h берется отображение множества я-слов в RA: Таким образом, эффективность фильтрации по составу растет при увеличении чис- ла букв алфавита и ограничена величиной (Л/2)1/2 (при больших η <?0=1,2 для нуклео- тидных последовательностей и е0 = 3,1 для аминокислотных последовательностей). Ока- зывается, что как в /-граммном анализе, так и в методе Миронова — Александрова увеличение эффективности фильтрации происходит за счет потенциального расширения исходного алфавита, причем в первом случае в качестве букв рассматриваются все слова длины /, а во втором — разнесенные динуклеотиды [29]. В следующем разделе показано, что в /-граммном анализе эффективность фильтрации растет как корень квад- ратный от числа букв в расширенном алфавите, т. е. как (А1)]/2. / - Г р а м м н а я ф и л ь т р а ц и я . При /-граммной фильтрации все слова из /-букв (/-граммы) кодируются числами от 1 до A1 и в качестве отображения h рас- ISSN 0233»7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1990. Т. 6. № 6 9 Детальный учет составляющих в последней формуле приводит к выражению: Отсюда следует, что и Здесь S1- — число букв вида і в слове S; А — размерность алфавита. Определим эффек- тивность фильтрации по составу для случая равновероятного появления букв. Для определения е необходимо получить значения математического ожидания M(d(S, T)) и дисперсии D(d(S, T)). Введем случайные величины: и обозначим Очевидно, что Для вычисления дисперсии оценим сначала M (d (S, T)2): Можно показать, что ненулевой вклад в M(d(S, T)2) вносят следующие пять со- ставляющих: сматривается: 10 ISSN 0233-7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1990. Т. 6. № 6 где s. —число l-грамм i-го вида в слове S. Подобно фильтрации по составу введем случайную величину и обозначим: В дальнейшем рассматриваются кольцевые слова 5 и T из ti букв — это позволяет из- бежать рассмотрения граничных эффектов, возникающих в начале и конце слов. Оче- видно, что 1, если начиная с і-го места в S стоит l-грамма а 0, в противном случае где /е — число букв в я, т. е. фактическая величина параметра / при /-граммной фильт- рации. Значение M (Xa i · xaj) при ІФ\ зависит от структуры самопересечений слова а. Зависимость вероятностных характеристик частот встречаемости слов от структуры их самопересечений изучена в [30, 31]. Мы будем говорить, что слово а допускает d-сдвиг, если ai^_d~a. при / = 1, k — d (через а. обозначена і-я буква слова а). Например, слово ATA допускает 2-сдвиг, а слово AAA — 1- и 2-сдвига. Очевидно, что M (xf = 0, если расстояние между позициями і и / больше или равно k (имеется в виду рас- стояние между позициями на кольцевой молекуле), в этом случае Xa i и л:? — независи- мые случайные величины (расстояние между позициями і и / обозначается \| j — /\|). Можно показать, что в случае, когда а допускает d-сдвиг, и расстояние между і и / равно d: где K d — множество слов, допускающих d-сдвиг, a K d —множество всех остальных слов. Учитывая, что объединение Kd и K d дает все множество /г-буквенных слов, по- лучим: Если же а не допускает d-сдвига, то до η равноправны, то Так как все позиции от 1 Так как = 0 при любом d и а общее число слов длины k равно Ak, то л4 и структуры самопересечений слов а и Ь. Очевидно, что если среди позиций л і , п2, /гЗ, /г4 найдется хотя бы одна изолированная (позиция называется изолированной, если расстояние от нее до каждой из трех оставшихся позиций больше или равно k), то t LJ Восемь типов конфигураций, рассматриваемых при оценке эффективности фильтрации (для каждой конфигурации представлены четыре слова, начинающиеся в позициях я1, п2, пЗ, п4). Конфигурация задается числами і, /, k, показывающими смещение п\, п2, яЗ, п4 относительно друг друга. Представленные на рисунке конфигурации здаются сле- дующими параметрами (конфигурации б—8 разбиваются на две пары неперекрываю- щихся слов): 1 — ровно одно из чисел /, k равно 0; 2— ί=ϋ, / > 0 , k—0; 3 — i = 0, 7 = 0, / е > 0 или г > 0 , / = 0, Aj = O; 4 - і = 0, / = 0, /г = 0; 5 — 0 , / > 0 , £ > 0 ; 6 — ί, / г > 0 и іф/г; 7 - і , / г > 0 и i = 8 — i = k = 0 Eight configuration types considered upon estimating the filtration efficiency (for each configuration 4 words beginning in positions til, n2, /гЗ, n4 are presented). The configu- ration is given by numbers i, j, k, that reveal shifts of positions η 1, м2, яЗ, n\ in respect to one another, The configurations presented are given by the following parameters (con- figurations 6-8 are subdivided to two pairs of non-overlapping words): 1 — exactly one of the numbers t, /, k is equal to zero; 2-і=0, / > 0 , k=0; 3-й=0, / = 0 , & > 0 or i > 0 , y = 0 , /г = 0; ί==0, / = 0, 6 = 0; 5 — i > 0 , / > 0 , /г>0; 5 - і , £ > 0 and 7 — і, & > 0 and і =/г ; 5 — і = k = 0 M (хп\хп2хп2>хпд ~ Следовательно, ненулевой вклад в M (d(S, T)) могут давать толь- ко четверки п\, я2, пЗ, п4, содержащие перекрывающиеся слова (такие четверки мы будем называть конфигурациями). Введем 8 типов конфигураций Fv—Fs (рисунок) и представим выражение M(d(S, T)) в виде: ISSN 02ЭЗ-7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1990. Т. 6. № 6 11 Для^вычисления M(d(S, Г)2) заметим: Значение зависит от взаимного расположения позиций /ї ї , л2, яЗ, Величина Vi существенно зависит от возможности самопересечений слов, входя- щих в конфигурацию. Детальный учет составляющих показывает, что: Для k = 2 точная формула для D (d (S, T)) имеет вид: Результаты и обсуждение. Несмотря на значительные усилия в течение последних двух десятилетий при поиске гомологии двух после- довательностей до сих пор неизвестны алгоритмы с линейной (или хо- тя бы значительно более низкой, чем квадратичная) трудоемкостью. В связи с отсутствием линейных по вычислительной сложности алго- ритмов было бы целесообразно разработать алгоритмы, трудоемкость которых является линейной в среднем. Эта задача даже для случая максимальной общей подпоследовательности до сих пор не решена. Представляется существенным для разработки такого алгоритма ис- пользовать методы фильтрации, применяющиеся при быстром поиске гомологий по банкам генетической информации. Настоящая работа яв- ляется попыткой решения проблемы именно в этом направлении, хотя полученные в ней оценки для эффективности фильтрации еще не поз- воляют утвердительно ответить на вопрос о существовании линейного в среднем алгоритма для проблемы максимальной общей подпоследо- вательности. Следует также отметить, что в работе получены только оценки параметров функции распределения статистического расстоя- ния, а вопрос о виде этой функции (и возможности ее аппроксимации) остается открытым. Автор выражает признательность Η. Н. Александрову, А. М. Леон- товичу, А. А. Миронову и А. В. Финкельштейну за обсуждение алго- ритмов быстрого поиска гомологий и В. Г. Тимковскому — за обсуж- дение проблем вычислительной сложности задачи поиска максимальной общей подпоследовательности. FILTRATION EFFICIENCY IN RAPID HOMOLOGY SEARCH STATISTICAL ALGORITHMS P. A. Pevzner Mathematical Laboratory of the Institute for Genetics of Microorganisms, Moscow, USSR S u m m a r y Upon searching local homologies in long sequences (homology search in nucleotide and amino acid sequences banks, selection of optimal oligonucleotide probes etc.) the neces- sity of a «rapid» homology search becomes acute. Quadratic complexity of the dymanic programming algorithms (Needleman—Wunsch and Sellers type) forces the employment of filtration methods, that permits one to reject the sequences with a low homology le- vel (among the filtration methods the 1—tuple analysis and the statistical method of Mironov—Alexandrov were used). But theoretical substantiations of such algorithms have not been made yet. The present work introduces the notion of filtration efficiency and the efficiency of several filters is given. It was shown that in the 1—tuple analysis the filtration efficiency is associated with the potential extension of the original four— letter alphabet. The formulas that allow choosing the filtration parameters are presented. СПИСОК ЛИТЕРАТУРЫ 1. Needleman S. В., Wunch С. D. A general method1 applicable to the search for simila- rities in the amino acids sequences of two p ro te ins / / J . MoL Biol.— 1970 - 48, N 2.— P. 443—453. 2. Sellers P. H. On the theory and computations of evolutionary d is tance / /SIAM J. Appl. Math.— 1974.'— 26, N 4.—P. 787—793. 3. Smith T. F., Waterman M. S., Burks C. The statistical distribution of nucleic acids similarities / / Nucl. Acids Res.— 1985 — 13, N 2.— P. 645—656. 4. Parallel computing'85/A. Lyall, C. Hill, J. F. Collins, A. F. W. Coulson/Eds M. Fel- meier et al.—North-Holland, 1986.—P. 235—258. 5. Gotoh O., Tagashira Y. Sequence search on supercomputer//Nucl. Acids Res.— 1986.— 14, N 1.—P. 57—64. 6. Collins J. F., Coulson A. F. W. Applications of parallel processing algorithms for DNA sequence analysis / / Ibid.— 1984.— 12, N 1.—P. 181—192. 12 ISSN 0233-7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1990. Т. 6. № 6 7. Goad W. В., Kanehisa Μ. I. Pattern recognition in nucleic acids sequences. 1. A gene- ral method for finding local homologies and symmetries//Ibid.— 19'82.— 10, N 1.— P. 247—263. 8. Masck W. /., Paterson M. S. How to compute string-edit distance quickly / / Time warps, string edits and macromolecules: the theory and practice of sequence com- parison.—Addison-Wesley, 1983,—P. 337—349. 9. Ukkonen E. On approximate string matching : Proc. Int. Conf. Found. Сотр. Theor. Lecturc notes in computer / / Science.— 1983.— 158.— P. 487—496. 10. Ройтбсрг Μ. А. Алгоритм определения гомологии первичных структур.— ГІущино, 1984,— 24 е.— (Препринт/АН СССР. НИВЦ АН СССР). 11. Hsu W7. /., Du Μ. V. New algorithms for LCS problem / / J . Comput. Syst. Sci.— 1984.—29, N 2 —P. 133—152. 12. Kumar S. K, Rangan C. P. A linear space algorithm for the LCS problem//Acta inf.— 1987.— 24.— P. 353—362. 13. Гусев В. Д., Куличков В. Α., Титкова Т. Н. Анализ генетических текстов. 1. L- граммные характеристики//Вычислительные системы.— 1980.— 83, № 1.— С. 11—33. 14. Fondrat С., Dessen P., Le Beux P. Principle of codification for quick comparison with the entire biomolecule databanks / / Nuck. Acids Res.— 1986.— 14, N 1.— P. 197—204. 15. Колчанов I f . А., Соловьев В. ВЖарких А. А. Контекстные методы теоретического анализа генетических макромолекул (ДНК, РНК и белков // Итоги науки и техни- ки,—М. : ВИНИТИ, 1985.—С. 6— 34.— (Молекуляр. биология; Т. 21). 16. Mironov A. A., Alexandrov N. N. Statistical methodjor rapid homology search//Nucl. Acids Res.— 1988 — 16, N 11.—P. 5169—5174. 17. Соловьев В. В., Рогозин И. Б. Быстрый поиск гомологий по банкам нуклеотидных и аминокислотных последовательностей//Теорет. исследования и банки данных по молекуляр. биологии и генетике.— Новосибирск, 1988.— С. 40. 18. Жарких А. А., Ржецкий А. Ю„ Родин С. Н. Оценка гомологии последовательностей по частотам олигонуклеотидов. I. Ограничения на состав нуклеотидов в ДНК.— Новосибирск, 1988.— 25 с.— (Препринт / АН СССР. Ин-т цитологии и ге- нетики). 19. Жарких А. А., Ржецкий А. Ю. Оценка гомологии последовательностей по частотам олигонуклеотидов. IL Анализ распределения замен в. нуклеотидных последователь- ностях. П-статистика.— Новосибирск, 1988.—26 е.— (Препринт / АН СССР. Ин-т цитологии и генетики). 20. Жарких Α.. А., Ржецкий А. Ю. Определение гомологии последовательностей по час- тотам олигонуклеотидов / / Теорет. исследования и банки данных по молекуляр. био- логии и генетике.— Новосибирск, 1988.— С. 40. 21. Срелец В. Б., Шиндялов И. Я. Быстрый поиск сходства между аминокислотными последовательностями//Там же.— С. 53. 22. Стрелец В. Б., Шиндялов И. Н. Быстрые методы поиска сходства между амино- кислотными последовательностями.— Новосибирск, 1988.— 25 с.— (Препринт/АН СССР. Ин-т цитологии и генетики). 23. Wilbur W. J., Lipman D. /."Rapid similarity searches on nucleic acids and protein data banks / /P roc . Nat. Acad. Sci. USA.— 1983.—80, N 2,— P. 726—730. 24. Kanehisa M. Use of statistical criteria for screening potential homologies in nucleic acids sequences / / Nucl. Acids Res.— 1984.— 12, N 1.— P. 203—214. 25. Lipman D. J., Pearson W. R. Rapid and sensitive similarity searches / / Science.— 1985.—227, N 6.—P. 1435—1440. 26. Blaisdell B. E. A measure of the similarity of sets of sequences not requiring sequence a l ignment / /Proc . Nat. Acad. Sci. USA.— 19ββ.— 83, N 10 — P . 5156— 5159. 27. Lawrence С. B., Goldman D. A., Hood R. T. Optimized homology searches of the gene and protein sequence data banks / /Bu l l . Math. Biol— 1986.—48, N 5/6 — P. 569— 583. 28. Zhurkin V. B. Periodicity in DNA primary structure is defained by secondary struc- ture of the coded prote in/ /Nucl . Acids Res.i—1981.—9, N 5.—P. 1963—1971. 29. Певзнер П. А. Эффективность фильтрации в методах быстрого поиска гомологий // Теорет. исследования и банки данных по молекуляр. биологии и генетике.— Ново- сибирск, 1988.—С. 63—64. 30. Guibas L. /., Odlyzko А. М. String overlaps, pattern matching and nontransitive ga- m e s / / J . Combin. Theory. Α.— 1981.—23.—P. 183—208. 31. Pevzncr P. A., Borodovsky M. Yu., Mironov A. A. Linguistics of nucleotide sequen- ces 1: the significance of deviations from mean statistical characteristics and pre- diction of the frequencies of occurence of w o r d s / / J . Biomol. Struct, and Dyn.— 6, N 5,— 1989.—P. 1013—1026. ВНИИ генетики и селекции пром. микроорганизмов, Получено 06.06.90 Москва ISSN 0233-7657. БИОПОЛИМЕРЫ И КЛЕТКА. 1990. Т. 6. № б 13

Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии

Репозитарії

Схожі ресурси