Помощь в написании студенческих работ
Антистрессовый сервис

Методы выравнивания биологических последовательностей, не использующие штрафы за делеции

Диссертация: Методы выравнивания биологических последовательностей, не использующие штрафы за делеции
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Показано, что наилучшее по точности выравнивание Смита-Ватермана в случае слабогомологичных последовательностей и использования матриц семейства РАМ получается при значении параметра СЕР = 1.0. Построена база данных эталонных выравниваний Р11ЕЕАВ-Р, которая может быть использована для оценки точности различных алгоритмов парного глобального выравнивания последовательностей. Предложена новая… Читать ещё >

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

Содержание

  • 1. Общая характеристика работы
    • 1. 1. Актуальность темы
    • 1. 2. Цели и задачи исследования
    • 1. 3. Теоретическая и практическая значимость
  • 2. Основные понятия
    • 2. 1. Выравнивания последовательностей
    • 2. 2. Многокритериальное выравнивание
    • 2. 3. Меры качества выравниваний
  • 3. Структура работы
  • Глава 1. Обзор литературы
    • 1. 1. Выравнивание символьных последовательностей
      • 1. 1. 1. Постановка задачи парного выравнивания символьных последовательностей
      • 1. 1. 2. Использование динамического программирования при выравнивании последовательностей
      • 1. 1. 3. Весовые матрицы замен
    • 1. 2. Базы данных эталонных выравниваний
      • 1. 2. 1. Общие сведения
      • 1. 2. 2. Обзор существующих баз данных
  • Глава 2. Эталонные выравнивания
    • 2. 1. База данных РИЕРАВ-Р
      • 2. 1. 1. Общие сведения
      • 2. 1. 2. Методика подготовки базы РЯЕРАВ-Р
      • 2. 1. 3. Структура базы данных PREFAB-Р
    • 2. 2. Модельные эталонные выравнивания
      • 2. 2. 1. Общие сведения
      • 2. 2. 2. Предварительные эксперименты
      • 2. 2. 3. Общая схема построения набора модельных данных
      • 2. 2. 4. Внесение мутаций-«замеп» в символьные последовательности
  • Глава 3. Алгоритм и реализация
    • 3. 1. Исследование алгоритма Смита-Ватермана
      • 3. 1. 1. Общие сведения
      • 3. 1. 2. Методика проведения экспериментов
      • 3. 1. 3. Результаты
    • 3. 2. Постановка новой задачи
      • 3. 2. 1. Исключение параметра GEP
      • 3. 2. 2. Формальная постановка задачи
    • 3. 3. Решение задачи построения набора выравниваний-кандидатов
      • 3. 3. 1. Общие сведения
      • 3. 3. 2. Алгоритм построения множества Парето-оптимальных выравниваний
      • 3. 3. 3. Алгоритм выделения основных выравниваний
      • 3. 3. 4. Оценка вычислительной сложности алгоритмов
    • 3. 4. Реализация
      • 3. 4. 1. Общие сведения
      • 3. 4. 2. Пользовательский интерфейс комплекса PARCA
      • 3. 4. 3. Программный интерфейс комплекса PARCA
      • 3. 4. 4. Детали реализации
    • 3. 5. Вспомогательные алгоритмы
      • 3. 5. 1. Определение штрафа GOP для соответствующих выравниваний Смита-Ватермана
      • 3. 5. 2. Выделение общей части основных выравниваний
  • Глава 4. Компьютерные эксперименты
    • 4. 1. Методика
      • 4. 1. 1. Общие сведения
      • 4. 1. 2. Построение выравниваний
      • 4. 1. 3. Анализ полученных данных
    • 4. 2. Анализ модельных данных
    • 4. 3. Анализ выравниваний из РЫЕКАВ-Р
    • 4. 4. Обсуждение результатов

1. Общая характеристика работы.

1.1.

Актуальность темы

.

Выравнивание аминокислотных и нуклеотидных последовательностей является классическим для биоинформатики методом сравнения последовательностей. Выявляемые при этом сходства часто являются следствием функциональных, структурных или эволюционных взаимосвязей между последовательностями. В 70-е годы XX века, когда сравнивались последовательности относительно небольшой длины, выравнивание производилось вручную, затем были предложены алгоритмы построения выравнивания [1, 2]. Актуальность задачи выравнивания символьных последовательностей обуславливается тем, что для многих белков известны их аминокислотные последовательности, но лишь для малой части из них известны пространственные структуры.

Для приложений важно, насколько алгоритмически полученные выравнивания отражают реальную эволюционную связь между сравниваемыми последовательностями. Количественной мерой этого служит точность выравнивания — доля таких сопоставлений эталонного выравнивания, которые присутствуют в алгоритмическом выравнивании. В качестве эталонных выравниваний аминокислотных последовательностей, как правило, используются выравнивания, основанные на наложении пространственных структур белков, соответствующих этим последовательностям.

Наиболее точным из известных в настоящее время алгоритмов построения глобального парного выравнивания аминокислотных последовательностей является алгоритм Смита-Ватермана[2]. Он основан на построении оптимального выравнивания, то есть выравнивания, для которого достигается максимальное значение соответствующей весовой функции. Тем не менее, для слабогомологичных последовательностей точность выравниваний Смита-Ва-термана невысока.

Существующие на данный момент алгоритмы попарного выравнивания, в частности, алгоритм Смита-Ватермана, требуют задания ряда параметров, выбор значений которых не имеет под собой надежного обоснования. Примером такого параметра является штраф за делецию (удаление) фрагментаошибка в выборе его значения приводит к существенному ухудшению точности алгоритмически полученного выравнивания. Одним из путей повышения точности алгоритмически построенных выравниваний является разработка метода выравнивания, который не использует штрафы за делеции, что определяет актуальность темы исследования.

Заключение

.

В рамках данной работы были получены следующие результаты.

1. Предложена новая постановка задачи глобального выравнивания биологических последовательностей — задача построения заданного количества ранжированных выравниваний-кандидатов.

2. Предложен алгоритм построения упорядоченного набора выравниваний-кандидатов, который не использует штрафы за удаления фрагментов.

Время работы алгоритма составляет 0(R • L2), где R — ограничение сверху на количество удаленных фрагментов в рассматриваемых выравниваниях, L — ограничение сверху на длину сравниваемых последовательностей.

3. Предложенный алгоритм реализован в виде общедоступного программного комплекса PARCA [3] и соответствующего веб-сервиса [4].

4. Проведены вычислительные эксперименты на модельных и реальных тестовых данных, позволяющие сравнить точность наборов выравниваний, получаемых с помощью предложенного алгоритма и точность выравниваний Смита-Ватермана.

5. Показано, что наилучшее по точности выравнивание Смита-Ватермана в случае слабогомологичных последовательностей и использования матриц семейства РАМ получается при значении параметра СЕР = 1.0.

6. Построена база данных эталонных выравниваний Р11ЕЕАВ-Р [5], которая может быть использована для оценки точности различных алгоритмов парного глобального выравнивания последовательностей .

Показать весь текст

Список литературы

  1. NeedlemanS. В., WunschC. D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 1970, vol. 48, pp. 443−453
  2. Smith T. F., Waterman M.S. Identification of common molecular subsequences. J. Mol. Biol. 1981, vol. 147, pp. 195−1973. http://server2.1pm.org.ru/static/download/parca/4. http://server2.1pm.org.ru/bio/pareto/5. http://server2.lpm.org.ru/static/prefab-p/
  3. Ройтберг M. A. IJapemo-оптимальные выравнивания символьных последовательностей. Пущино: ОНТИ НЦБИ, 1994. Препринт, 10 с.
  4. М. А., Семионенков М. Н., Таболина О. Ю. Парето-опти-мальные выравнивания биологических последовательностей. Биофизика. 1998, Т. 44, № 4, стр. 581−594
  5. Pareto V. Manual of political economy. New York: A. M. Kelley, 1972
  6. AsthanaS., RoytbergM., StamatoyannopoulosJ., SunyaevS. Analysis of sequence conservation at nucleotide resolution. PLoS Comput Biol. 2007, vol.3, N. 12, p. 254
  7. О. M., Астахова Т. В., Власов П. К., Ройтберг М. А. Статистический анализ участков ДНК в окрестности сайтов сплайсинга. Молекулярная биология. 2008, т. 42, № 1, стр. 150−162
  8. LeskA.M. Introduction to protein architecture. Oxford, N.Y.: Oxford Univ. press. 2001. P.360
  9. PirovanoW., FeenstraK. A., HeringaJ. The meaning of alignment: lessons from structural diversity. BMC Bioinformatics. 2008, vol. 9, p. 556
  10. KisterA.E., RoytbergM.A., ChothiaC., Gelfandl.M. The sequence determinants of cadherin molecules. Protein Science. 2001, vol. 10, pp. 1801−1810
  11. NotredameC., HigginsD.G., HeringaJ. T-Coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 2000, vol. 302, pp. 205−217
  12. Thompson J. D., HigginsD.G., Gibson T.J. CLUSTALW: improving the sensitivity of progressive multiple sequence alignment through sequence eighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res. 1994, vol. 22, pp. 473−480
  13. KatohK., KumaK., TohH., MiyataT. MAFFT version5: Improvement in Accuracy of Multiple Sequence Alignment. Nucleic Acids Research. 2005, vol.3, pp. 511−518
  14. Edgar R. C. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research. 2004, vol. 32, N. 5, pp. 1792−1797
  15. Edgar R. C, BatzoglouS. Multiple Sequence Alignment. Current Opinion in Structural Biology. 2006, vol. 16, pp. 368−373
  16. Russell D., OutH., SayoodK. Grammar-based distance in progressive multiple sequence alignment. BMC Bioinformatics. 2008, vol. 9, p. 306
  17. Rice P., LongdenL, BleasbyA. EMBOSS: The European Molecular Biology Open Software Suite Trends in Genetics 2000, vol. 16, N. 6, pp. 276−277
  18. NazipovaN. N., ShabalinaS. A., Ogurtsov A. Yu., Kondrashov A. S., RoytbergM.A., BuryakovG.V., VernoslovS.E. SAMSON: a software package for the biopolymer primary structure analyses. Comput. Appl. Biosci. 1995, vol. 11, N. 4, pp. 423−426
  19. ЛевенштейнВ. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР. 1965. Т. 163, № 4. С. 845−848
  20. UlamS.M. Some Ideas and Prospects in Biomathematics. Annu Rev Biophys Bioeng. 1972, vol. 1, p. 277
  21. KruskalJ.B. An Overview of Sequence Comparison: Time Warps. String Edit and Macromoleculas. SIAM Rev. 1983, vol. 25, N. 26, pp. 201−238
  22. RochkindM. J. The Source Code Control System. IEEE Transactions on Software Engineering. 1975, vol. 1, N. 4, pp. 364−370
  23. Waterman M.S. Introduction to Computational Biology. London: Chapman and Hall Press. 1995
  24. Cartwright. R. A. Logarithmic gap costs decrease alignment accuracy. BMC Bioinformatics. 2006, vol. 7, p. 527
  25. GonnetG. H, Cohen M. A, BennerS. A. Exhaustive matching of the entire protein sequence database. Science. 1992, vol. 256, N. 5062, pp. 1443−1445
  26. ZvelebilM., BaumJ.O. Understanding bioinformatics. London: Garland Science. 2007. 800 p.
  27. Waterman M.S. Sequence alignments in the neighborhood of the optimum with general application to dynamic programming. PNAS. 1983, vol. 80, N. 10, pp. 3123−3124
  28. ByersT. M., Waterman M.S. Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming. Oper Res. 1984, vol. 32, pp. 1381−1384
  29. VingronM., ArgosP. Determination of reliable regions in protein sequence alignments. Protein Engineering. 1990, vol. 3, N. 7, pp. 565−569
  30. ZukerM. Suboptimal sequence alignment in molecular biology. Alignment with error analysis. J. Mol. Biol. 1991, vol.221, N. 2, p. 403
  31. Fitch W. M., Smith T. F. Optimal sequence alignments. Proc. Natl. Acad. Sci. USA. 1983, vol.80, pp. 1382−1386
  32. Waterman M. S., EggertM., Lander E. Parametric sequence comparisons. Proc.Nat. Acad. Sci. USA. 1992, vol.89, pp. 6090−6093
  33. Fernandez-Baca. D., SrinivasamS. Constructing tile minimization diagram of a two-parameter problem. Operat. Res. Letters. 1991, vol.10, pp. 87−93
  34. GusfieldD., BalasubramianK., NaorK. Proc. 3rd Ann. ACM-SIAM Discrete Algorithms. 1992, pp. 432−439
  35. Bellman R. On the theory of dynamic programming. Proc. Nat. Acad. Sci. U.S.A. 1952, vol.38, pp. 716−719
  36. KleeneS.C., Representation of events in nerve nets and finite automata. Shannon C.E., McCarthy J. (Eds.), Automata Studies, Princeton University Press. 1956. P. 3−41
  37. McNaughtonR., YamadaH. Regular expressions and state graphs for automata. IRE Transactions on Electronic Computer. 1960, vol.9, N. 1. pp.39−47
  38. Kramers H. A., Wannier G. H. Statistics of the one-dimensional ferromagnet. Phys. Rev. 1941, vol.60, pp. 252−276
  39. AhoA., HopcroftJ., UlmanJ. The design and analysis of computer algorithms. Addison-Wesley, Reading, MA., USA. 1974. P.470
  40. GelfandM.S., Podolsky L. I., AstakhovaT. V., RoytbergM.A. Prediction of the exon-intron structure and multicriterial optimization. Bioinformatics and Genome Research (H.A.Lim, C.R.Cantor, eds.). World Scientific Publ. Co., Singapore. 1995. PP. 173−183
  41. RoytbergM.A., AstahovaT.V., GelfandM.S. Combinatorial approaches to gene recognition. Computers and Chemistry. 1998, vol. 1, N. 21, pp. 229−236
  42. RamenskyV.E., MakeevV.Ju., RoytbergM.A., Tumanyan.V.G. DNA segmentation through the Bayesian approach. J. Comput. Biol. 2000, vol. 7, N. 1−2, p. 215−31
  43. Ramensky V.E., MakeevV. Y., RoytbergM. A., TumanyanV. G. Segmentation of long genomic sequences into domains with homogeneous composition with BASIO software. Bioinformatics. 2001, vol. 17, N. 11, pp. 1065−1066
  44. Vogt G., EtzoldT., ArgosP. An assessment of amino acid exchange matrices in aligning protein sequences: the twilight zone revisited. J. Mol. Biol. 1995, vol. 249, pp. 816−831
  45. GribskovM, VeretnikS. Identification of sequence pattern wit hprofile analysis. Methods Enzymol. 1996, vol. 266, pp. 198 -212
  46. Sunyaev S. R., Bogopolsky G. A., OleynikovaN. V., VlasovP.K., FinkelsteinA.V., RoytbergM.A. From analysis of protein structural alignments toward a novel approach to align protein sequences. Proteins. 2004, vol. 54, pp. 569−582
  47. Huang X., ChaoK.-M. A generalized global alignment algorithm. Bioinformatics. 2003, vol. 19, no. 2, pp. 228−233
  48. DayhoffM. O., Schwartz R. M., Orcutt B. C. A model of evolutionary change in proteins. Atlas of Protein Sequence and Structure. 1978, vol. 5, suppl. 3, pp.345−35 252. http://www.biorecipes.com/Dayhoff/code.html
  49. Polyanovsky V., Roytberg M., Tumanyan V. Reconstruction of genuine pair-wise sequence alignment. Computational Biology. 2008, vol. 15, N. 4. pp. 379−391
  50. HenikoffS., HenikoffJ. G. Amino Acid Substitution Matrices from Protein Blocks. PNAS. 1992, 89(22), pp. 10 915−10 919
  51. Smith R. F. and Smith T.F. Pattern-induced multi-sequence alignment (PIMA) algorithm employing secondary structure-dependent gap penalties for use in comparative protein modelling. Protein Eng. 1992, vol. 5, pp. 35−41
  52. DeperieuxE., BaudouxG., BriffeuilP., ReginsterL, DeBolleX., VinalsC. and FeytmansE. MATCH-BOX server: a multiple sequence alignmenttool placing emphasis on reliability. Comput. Appl. BioSci. 1997, vol. 13, pp.249−256
  53. Thompson J. D., GibsonT. J, PlewniakF., JeanmouginF. and HigginsD.G. The CLUSTALX windows interface: flexible strategies for multiple sequence aligment aided by quality analysis tools. Nucleic Acids Res. 1997, 24, pp. 4876−4882
  54. Edgar R. C. Quality measures for protein alignment benchmarks. Nucleic Acids Res. 2010, vol. 38, pp. 2145−2153
  55. BermanH. M. et al. The Protein Data Bank. Nucleic Acids Res. 2010, vol. 28(1), pp. 235−242
  56. Cochrane G. el.al. Petabyte-scale innovations at the European Nucleotide Archive. Nucleic Acids Research. 2009, vol. 37, pp. 19−2561. http: //www. uniprot. org/
  57. MurzinA. G., Brenner S.E., Hubbard T. and ChothiaC. SCOP: a structural classification of proteins database for the investigation of sequences and structures. J. Mol. Biol. 1995, 247, pp. 536−540
  58. OrengoC., MichieA., JonesS., Jones D., Swindells M. and Thornton J. CATH a hierarchic classification of protein domain structures. Structure.1997, vol. 5, pp. 1093−110 864. http://www.drive5.com/muscle/prefab.htm
  59. Thompson J. D., PlewniakF., PochO. BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics.1998, vol. 15, pp. 87−88
  60. VanWalleL, LastersL, WynsL. SABmark a benchmark for sequence alignment that covers the entire known fold space. Bioinformatics. 2005, vol.21, pp. 1267−1268
  61. MizuguchiK., DeaneC.M., BlundellT. L., Overington J. P. HOMSTRAD: a database of protein structure alignments for homologous families. Protein Sci. 1998, vol. 7, pp. 2469−2471
  62. RaghavaG. P., SearleS.M., AudleyP.C., Barber J. D., Barton G.J. OXBench: a benchmark for evaluation of protein multiple sequence alignment accuracy. BMC Bioinformatics. 2003, vol. 4, p. 4769. http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html
  63. SadreyevR. and GrishinN. COMPASS: a tool for comparison of multiple protein alignments with assessment of statistical significance. J. Mol. Biol. 2003, N. 326, pp. 317−336
  64. R. С. and SjolanderK. A comparison of scoring functions for protein sequence profile alignment. Bioinformatics. 2004, DOI: 10.1093/bioinformatics/bth090
  65. HolmL. and Sander C. Touring protein fold space with Dali/FSSP. Nucleic Acids Res. 1998, 26, pp. 316−319
  66. Shindyalovl. N. and Bourne P. E. CE: A Resource to Compute and Review 3-D Protein Structure Alignments. Nucleic Acid Research. 2001, 29(1), pp.228−229
  67. Т. В., Поверенная И. В., Ройтберг М. А, Яковлев В.В. Верификация базы эталонных выравниваний PREFAB. Биофизика. 2012, Т. 57, № 2, стр. 205−211
  68. PoverennayaL, LobanovM., YacovlevV., RoytbergM. Using of PREFAB for analysis of amino-acid sequence alignment algorhitms. Proc, MCCMB’ll. p. 327
  69. К. Дж. Дейт Введение в системы баз данных 7-е изд. -М.: Вильяме, 2001. — С. 1072
  70. Waterman М. S. Mathematical methods for DNA sequences. Boca Raton, FL: CRC Press, 198 978. http://www.python.org/79. http://www.boost.org/
  71. Tanenbaum A. S. Operating Systems: Design and Implementation. -Prentice Hall, 1987. 719 P.
  72. A. M. Операционная система UNIX. -СПб.: БХВ, 2002. -С. 52 682. http://fasta.bioch.Virginia.edu/fastawww2/fastalist2.shtml
  73. Pearson WR, Lipman DJ. Improved tools for biological sequence comparison. Proc Natl Acad Sci USA. 1988, vol 85. pp. 2444−2448
  74. В. В., Ройтберг М. А. Увеличение точности глобального выравнивания аминокислотных последовательностей с помощью построения набора выравниваний-кандидатов. Биофизика. 2010, Т. 55, № 6, стр. 965−975
  75. И. В., Ройтберг М. А., Яковлев В. В. Эффективность использования программы PARCA для глобального выравнивания аминокислотных последовательностей. Информационные процессы. 2011, Т. 11, № 4, стр. 510−519
Заполнить форму текущей работой

Сессия? Спокойно!