Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбр...
Saved in:
| Published in: | Биополимеры и клетка |
|---|---|
| Date: | 1990 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут молекулярної біології і генетики НАН України
1990
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/154122 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862620463762505728 |
|---|---|
| author | Певзнер, П.А. |
| author_facet | Певзнер, П.А. |
| citation_txt | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос. |
| collection | DSpace DC |
| container_title | Биополимеры и клетка |
| description | При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбраковать» последовательности с низким уровнем гомологии. В работе вводится понятие эффективности фильтрации и дается оценка эффективности некоторых фильтров, при этом показано, что в 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.
|
| first_indexed | 2025-12-07T13:22:09Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-154122 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0233-7657 |
| language | Russian |
| last_indexed | 2025-12-07T13:22:09Z |
| publishDate | 1990 |
| publisher | Інститут молекулярної біології і генетики НАН України |
| record_format | dspace |
| spelling | Певзнер, П.А. 2019-06-15T08:09:07Z 2019-06-15T08:09:07Z 1990 Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос. 0233-7657 DOI: http://dx.doi.org/10.7124/bc.000299 https://nasplib.isofts.kiev.ua/handle/123456789/154122 519.764 При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбраковать» последовательности с низким уровнем гомологии. В работе вводится понятие эффективности фильтрации и дается оценка эффективности некоторых фильтров, при этом показано, что в 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. Автор выражает признательность Η. Н. Александрову, А. М. Леонтовичу, А. А. Миронову и А. В. Финкельштейну за обсуждение алгоритмов быстрого поиска гомологий и В. Г. Тимковскому — за обсуждение проблем вычислительной сложности задачи поиска максимальной общей подпоследовательности. ru Інститут молекулярної біології і генетики НАН України Биополимеры и клетка Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии Ефективність фільтрації у статистичних алгоритмах швидкого пошуку гомології Filtration efficiency in rapid homology search statistical algorithms Article published earlier |
| spellingShingle | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии Певзнер, П.А. |
| title | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_alt | Ефективність фільтрації у статистичних алгоритмах швидкого пошуку гомології Filtration efficiency in rapid homology search statistical algorithms |
| title_full | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_fullStr | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_full_unstemmed | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_short | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_sort | эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/154122 |
| work_keys_str_mv | AT pevznerpa éffektivnostʹfilʹtraciivstatističeskihalgoritmahbystrogopoiskagomologii AT pevznerpa efektivnístʹfílʹtracííustatističnihalgoritmahšvidkogopošukugomologíí AT pevznerpa filtrationefficiencyinrapidhomologysearchstatisticalalgorithms |