Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии
При поиске локальных гомологий, (поиск гомологий в генетических банках, выбор оптимальных олигонуклеотидных зондов и т. п.) возникает проблема их «быстрого» поиска. Квадратичная трудоемкость алгоритмов динамического программирования заставляет прибегать к методам фильтрации, позволяющим быстро «отбр...
Gespeichert in:
| Veröffentlicht in: | Биополимеры и клетка |
|---|---|
| Datum: | 1990 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут молекулярної біології і генетики НАН України
1990
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/154122 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-154122 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| spellingShingle |
Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии Певзнер, П.А. |
| title_short |
Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_full |
Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_fullStr |
Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_full_unstemmed |
Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| title_sort |
эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии |
| author |
Певзнер, П.А. |
| author_facet |
Певзнер, П.А. |
| publishDate |
1990 |
| language |
Russian |
| container_title |
Биополимеры и клетка |
| publisher |
Інститут молекулярної біології і генетики НАН України |
| format |
Article |
| title_alt |
Ефективність фільтрації у статистичних алгоритмах швидкого пошуку гомології Filtration efficiency in rapid homology search statistical algorithms |
| 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.
|
| issn |
0233-7657 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/154122 |
| citation_txt |
Эффективность фильтрации в статистических алгоритмах быстрого поиска гомологии / П.А. Певзнер // Биополимеры и клетка. — 1990. — Т. 6, № 6. — С. 7-13. — Бібліогр.: 31 назв. — рос. |
| work_keys_str_mv |
AT pevznerpa éffektivnostʹfilʹtraciivstatističeskihalgoritmahbystrogopoiskagomologii AT pevznerpa efektivnístʹfílʹtracííustatističnihalgoritmahšvidkogopošukugomologíí AT pevznerpa filtrationefficiencyinrapidhomologysearchstatisticalalgorithms |
| first_indexed |
2025-12-07T13:22:09Z |
| last_indexed |
2025-12-07T13:22:09Z |
| _version_ |
1850855894513876992 |