Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбр...
Збережено в:
| Видавець: | Інститут молекулярної біології і генетики НАН України |
|---|---|
| Дата: | 1990 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут молекулярної біології і генетики НАН України
1990
|
| Назва видання: | Биополимеры и клетка |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/154122 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Цитувати: | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 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 |
2023-05-20T17:43:30Z |
| last_indexed |
2023-05-20T17:43:30Z |
| _version_ |
1796153942832316416 |