Теоретико-вероятностные и комбинаторные задачи теории кодирования ДНК-последовательностей тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Воронина, Анна Никитична

• Воронина, Анна Никитична
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Воронина, Анна Никитична

Список обозначений 2

1 Введение, постановка задачи и результаты 9

1.1 Биологическая мотивация .9

1.1.1 Последовательности ДНК и их свойства. .10

1.1.2 Описание эксперимента.13

1.1.3 Постановки задач.16

1.2 Математическая формализация и общие определения .18

1.2.1 Весовая функция для ДНК-стеблей.19

1.2.2 Стебельное сходство ДНК-последовательностей.20

1.2.3 ДНК-коды, основанные на стебельном сходстве.23

1.2.4 Постановки задач.25

1.3 Метод случайного кодирования для ДНК-кодов.26

1.4 Основные результаты диссертации .29

1.4.

Глава 2.31

1.4.

Глава 3.33

1.4.

Глава 4.36

1.4.

Глава 5.37

1.4.

Глава 6.40

1.5 Исторический обзор.43

2 Конструкции ДНК-кодов для стебельного расстояния 50

2.1 Обозначения и определения .50

2.2 Кодовые конструкции для ДНК-кодов, основанных на аддитивном стебельном 1-сходстве.52

2.2.1 ДНК-коды с проверкой на четность.52

2.2.2 Коды Рида-Маллера первого порядка.54

2.3 Объем ДНК-кодов для фиксированного сходства.62

2.4 Субоптимальные ДНК-коды, основанные на неаддитивном стебельном w-сходстве.68

3 Неасимптотические задачи для аддитивного стебельного - сходства 73

3.1 Аддитивное стебельное 1-сходство и его основные свойства.74

3.2 Вычисление объемов сфер.76

3.3 Неасимптотические оценки объема сферы.80

3.4 Асимптотика объема сферы.83

3.5 Объем ДНК-кода для фиксированного расстояния.87

4 Границы скорости ДНК-кодов для аддитивного стебельного -сходства 91

4.1 Обозначения, определения и примеры .91

4.2 Формулировки результатов.93

4.3 Доказательство теоремы 4.1.94

4.4 Доказательство теоремы 4.2.98

4.4.1 Граница случайного кодирования.98

4.4.2 Вычисление явного вида границы.100

4.5 Доказательства теорем 4.3 и 4.4.105

5 Границы скорости ДНК-кодов для аддитивного стебельного w -сходства 110

5.1 Обозначения, определения и примеры .111

5.2 Формулировки результатов.113

5.2.1 Границы скорости Rw(d).113

5.2.2 Критическая доля расстояния (n, dn)w -кодов для примеров 1.2 и 1.3 .116

5.3 Доказательство теоремы 5.1.118

5.4 Доказательство теоремы 5.2.120

5.4.1 Граница случайного кодирования.120

5.4.2 Нижняя оценка границы случайного кодирования .125

5.5 Анализ весовых образцов, основанный на критерии критической доли расстояния.126

5.5.1 Анализ таблиц 5.1-5.8 для аддитивного стебельного w -расстояния.128

5.5.2 Выводы.131

5.6 Решение задачи максимизации (5.7)-(5.10).132

6 Границы скорости ДНК-кодов для неаддитивного стебельного w -сходства 135

6.1 Обозначения и определения .136

6.2 Границы случайного кодирования.140

6.2.1 ДНК-коды для ансамблей Фибоначчи.140

6.2.2 Об объемах L -ансамблей Фибоначчи .143

6.2.3 Граница случайного кодирования для

L -ансамбля Фибоначчи.144

6.2.4 Граница случайного кодирования для ДНК (n, dn)^ -кодов .146

6.3 Анализ весовых образцов, основанный на критерии критической доли расстояния.147

6.3.1 Анализ таблиц 5.1-5.8 для неаддитивного стебельного w -расстояния.149

6.3.2 Выводы.150

6.4 Доказательство теоремы 6.1.150

6.4.1 Общая схема доказательства.150

6.4.2 Доказательство леммы 6.2.153

6.4.3 Доказательство леммы 6.3.155

6.4.4 Доказательство леммы 6.4.159

6.5 Обобщение теоремы 6.1.162

6.5.1 Верхние границы для решений линейных рекуррентных уравнений . 162

6.5.2 Граница случайного кодирования для L -ансамблей в общем случае.169

Список литературы диссертационного исследования кандидат физико-математических наук Воронина, Анна Никитична, 2010 год

1. Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн, Теория кодов, исправляющих ошибки, Москва: Связь, 1979.

2. R. G. Gallager, Information Theory and Reliable Communication, New York: J. Wiley, 1968. Перевод на русский язык: Р. Галлагер, Теория информации и надежная связь, Москва: Советское радио, 1974.

3. Э. Берлекемп, Алгебраическая теория кодирования, Москва: Мир, 1971.

4. Е. F. Assmus, Jr., J. D. Key, Designs and Their Codes, Cambridge: Cambridge University Press, 1992.

5. В. И. Левенштейн, "Двоичные коды с исправлением выпадений, вставок и замещений символов," Докл. Акад. Наук СССР, т. 163. п. 4. с. 845-848, 1965.

6. В. И. Левенштейн, "Элементы теории кодирования," в кн. Дискретная математика и математические вопросы кибернетики, Москва: Наука, 1974, с. 207-305.

7. V. I. Levenshtein, "Efficient Reconstruction of Sequences from Their Subsequences or Supersedences," J. Comb. Th., Ser. A, vol. 93, pp. 310-332, 2001.

8. V. Dancik, "Expected Length of Longest Common Subsequences," Ph.D. thesis, Univ. of Warwick, UK, 1994.

9. J. Yin, "A combinatorial construction for perfect deletion-correcting codes," Designs, Codes, and Cryptography, vol. 23, n. 1, pp. 99-110, 2001.

10. P. P. Варшамов, Г. M. Тененгольц, "Код, исправляющий одиночные несимметричные ошибки," Автоматика и телемеханика, т. 26, и. 2, с. 288-292, 1965.

11. N. Sloane, "On single-deletion-correcting codes," IEEE Trans. Inform. Theory, 2002.13| A. G. D'yachkov, D. C. Torney, "On similarity codes," IEEE Trans. Inform. Th., vol. 46, n. 4, pp.1558-1664, 2000.

12. A. G. D'yachkov, D. C. Torney, P. A. Vilenkin, P. S. White, "Reverse-Complement Similarity Codes for DNA Sequences," тезисы симпозиума ISIT-2000, Сорренто, Италия, 2000, с. 330.

13. A. G. D'yachkov, P. L. Erdos, A. J. Macula, V. V. Rykov, D. C. Torney, C. S. Tung, P. A. Vilenkin, P. S. White, "Exordium for DNA Codes," J. Comb. Optimization, vol. 7, n. 4, pp. 369-379, 2003.

14. А. Г. Дьячов, П. А. Виленкин, И. К. Исмагилов, Р. С. Сарбаев, А. Макула, Д. Торни, С. Уайт, "О ДНК кодах," Проблемны Передает Информации, т. 41, н. 4, с. 57-77, 2005.

15. A. G. D'yachkov, A. J. Macula, Т. Е. Renz, P. A. Vilenkin, I. К. Ismagilov, "New Results on DNA Codes," в Proc. 2005 IEEE Int. Symp. Information Theory, Аделаида, Южная Австралия, Автралия, 2005, с. 283-288.

16. А. Г. Дьячов, П. А. Виленкин, И. К. Исмагилов, Р. С. Сарбаев, А. Макула, Д. Торни, С. Уайт, "Письмо в редакцию," Проблемы Передачи Информации, т. 42, н. 2, с. 109109, 2006.

17. М. A. Bishop, A. G. D'yachkov, A. J. Macula, Т. Е. Renz, V. V. Rykov, "Free Energy Gap and Statistical Thermodynamic Fidelity of DNA Codes," Journal of Computational Biology, vol. 14, n. 8, pp. 1088-1104, 2007.

18. П. А. Виленкин, "Асимптотические задачи комбинаторной теории кодирования и теории информации," Диссертация на соискание ученой степени к.ф.-м.н. Москва, МГУ им. М.В.Ломоносова. 2000.

19. A. Marathe, А. Е. Condon, R. М. Corn, "On combinatorial DNA design," J. Сотр. Biol., vol. 8, pp. 201-219, 2001.

20. О. Milenkovic, N. Kashyap, "New Constructions of Codes for DNA computing," в Proc. 2005 International Workshop on Coding and Cryptography (WCC 2005), Берген, Норвегия, 2005, стр. 204-213.

21. R. Dirks, J. Bois, J. Schaeffer, et al., "Thermodynamic analysis of interacting nucleic acid strands," SI AM Rev., vol. 49, pp. 65-88, 2007.

22. J. SantaLucia, "A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics," Proc. National Academy of Sciences USA, vol. 95, pp. 14601465,1998.

23. J. SantaLucia, D. Hicks, "The thermodynamics of DNA structural motifs," Annu. Rev. Biophys. Biomol. Struct., vol. 33, pp. 415-440, 2004.

24. M. Andronescu, R. Aguirre-Hernandez, A. Condon, et al., "RNAsoft: a suite of RNA secondary structure prediction and design software tools Nucleic Acids Res., vol. 31, pp. 3416-3422, 2003. Также доступно на: http:// www.rnasoft.com.

25. R. Eason, N. Pourmand, W. Tongprasit, et al., "Characterization of synthetic DNA bar codes in Saccharomyces cerevisiae gene-deletion strains PNAS, vol. 101, pp. 11046-11051, 2004.

26. M. Shortreed, S. Chang, D. Hong, "A thermodynamic approach to designing structure-free combinatorial DNA word sets Nucleic Acids Res., vol. 33, pp. 4965-4977, 2005.

27. D. Tulpan, M. Andronescu, S. Chang, et al., "Thermodynamically based DNA strand design Nucleic Acids Res, vol. 33, pp. 4951-4964, 2005.

28. L. Kaderali, "Selecting target specific probes for DNA arrays," Master's Thesis, Informatics, U. Koln, 2001.

29. S. B. Needleman, C. D. Wunsch, "A general method applicable to the search for similarities in the amino-acid sequences of two proteins," J. Mol. Biol., vol. 48, pp. 443-453, 1970.

30. T. F. Smith, M. S. Waterman, "Identification of common molecular subsequences," J. Mol. Biol., vol. 147, pp. 195-197, 1981.

31. M. Bishop, A. Macula, T. Renz, SynDCode Suite, 2006. Доступно на: http://syndcode.geneseo.edu/.

32. J. Chen, R. Deaton, M. Garzon, "Characterization of Non-crosshybridizing DNA Oligonucleotides Manufactured in vitro," Natural Computing vol. 5, n. 2, pp. 165-181, 2006.

33. L. Kaderali, A. Deshpande, Л. Nolan, P. White, "Primer-design for multiplexed geno-typing," Nucleic Acids Res., vol. 31, pp. 1796-1802, 2003.

34. R. Penchovsky, J. Ackermann, "DNA library design for molecular computation," J. Compxit. Biol., vol. 10, pp. 215-229, 2003.

35. M. Mansuripur, P. K. Khulbe, S. M. Kuebler, J. W. Perry, M. S. Giridhar, N. Pey-ghambarian, "Information Storage and Retrieval using Macromolecules as Storage Media," Optical Data Storage Conference, Ванкувер, Канада, 2003.

36. H. Cai, P. White, D. Torney, et al., "Flow cytometry-based minisequencing: a new platform for high throughput single nucleotide polymorphism scoring," Genomics, vol. 66, pp. 135— 143, 2000.

37. D. Fish, M. Home, R. Searles, et al., "Multiplex SNP Discrimination," Biophysical Journal, vol .92, pp. 89-92, 2007.

38. M. Valignat, O. Theodoly, J. Crocker, et al., "Reversible self-assembly and directed assembly of DNA-linked micrometer-sized colloids," FN AS, vol. 102, pp. 4225-4229, 2005.

39. P. Hardenbol, J. Baner, M. Jain, et al., "Multiplexed genotyping with sequence-tagged molecular inversion probes," Nat. BiotechnoL, vol. 6, pp. 673-678, 2003.

40. E. K. Nordberg, "YODA: selecting signature oligonucleotides," Bioinformatics, vol. 21, n. 8, pp. 1365-1370, 2005.

41. X. Li, Z. He, J. Zhou, "Selection of optimal oligonucleotide probes for microarrays using multiple criteria, global alignment and parameter estimation," Nucleic Acids Res., vol. 33, n. 19, pp. 6114-6123, 2005.

42. R. Braich, N. Chelyapov, Johnson, et al., "Solution of a 20-Variable 3-SAT problem on a DNA computer," Sciencexpress, vol. 296, pp. 499-502, 2002.

43. J. Rose, R. Deaton, A. Suyama, "Statistical thermodynamic analysis and design of DNA-based computers," Natural Computing, vol. 3, pp. 443-359, 2004.

44. L. Adleman, "Molecular Computation of Solutions to Combinatorial Problems," Science, vol. 266. pp. 1021-1024, 1994.

45. Q. Ouyang, P. D. Kaplan, S. Liu, A. Libchaber, "DNA solution of the maximal clique problem," Science, vol. 278, pp. 446-449, 1997.

46. К. Sakamoto, Н. Gouzu, К. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, M. Hagiya, "Molecular computation by DNA hairpin formation," Science, vol. 288, pp. 1223-1226, 2000.

47. S. Tsaftaris, A. Katsaggelos, T. Pappas, E. Papoutsakis, "DNA Computing from a Signal Processing Viewpoint," IEEE Signal Processing Magazine, pp. 100-106, 2004.

48. A. Macula, S. Gal, C. Andam, Т. E. Renz, M. A. Bishop, "PCR nonadaptive group testing of DNA libraries for biomolecular computing and taggant applications," Discrete Mathematics, Algorithms and Applimtions, vol. 1, n. 1, pp. 59-69, 2009.

49. В. H. Тутубалин, Теория вероятностей и случайных процессов, Москва: Издательство МГУ, 1992.

50. A. Dembo, О. Zeitouni, Large Deviations Techniques and Applications, Boston, MA: Jones and Bartlett, 1993.

51. Э. Рейнгольд, Ю. Нивергельт, H. Део, Комбинаторные алгоритмы. Теория и практика, Москва: Мир, 1980.

52. P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, UK, 1994.

53. D. T. Tang, L. R. Bahl, "Block Codes for a Class of Constrained Noiseless Channels," Inform, and Control, v. 17, n. 5, pp. 436-461, 1970.

54. Handbook of combinatorics, edit. R. L. Graham, M. Grotschel, L. Lovasz, v. 2, MIT Press, 1995.Работы автора по теме диссертации

55. А. Г. Дьячков, А. Н. Воронина, "ДНК-коды для аддитивного стебельного сходства," Проблемы Передачи Информации, т. 45, н. 2, стр. 56—77, 2009.

56. А. Н. Воронина, "Об объч,мах сфер для стебельного расстояния," Проблемы Передачи Информации, т. 46, н. 1, стр. 9-19, 2010.

57. A. G. D'yachkov, А. N. Voronina, "DNA Codes Based on Stem Hamming Similarity," Proc. 11th Int. Workshop Algebraic and Combinatorial Coding Theory, Памнорово, Болгария, 2008, стр. 85-91.

58. А. Г. Дьячков, А. Н. Воронина, "ДНК-коды, основанные на весовом стебельном сходстве Хэмминга," Сборник трудов ИТиС'08, Геленджик, Россия, 2008, стр. 316-320.