Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений

Подождите немного. Документ загружается.

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

[241] Gh. P˘aun. The splicing as an operation on formal languages.

[INBS], 176–180.

[242] Gh. P˘aun. Splicing. A challenge to formal language theorists. Bull.

EATCS, 57 (1995), 183–194, см. также [CTCS], 830–844.

[243] Gh. P˘aun. Regular extended H systems are computationally

universal. J. Automata, Languages, Combinatorics, 1 (1996), 27–

36.

[244] Gh. P˘aun. On the power of splicing grammar systems. Ann. Univ.

Buc., Matem.-Inform. Series, 45 (1996), 93–106.

[245] Gh. P˘aun. Five (plus two) universal DNA computing models based

on the splicing operation. [DNA2], 67–86.

[246] Gh. P˘aun. Computing by splicing: How simple rules? Bull. EATCS ,

60 (1996), 145–150.

[247] Gh. P˘aun. Splicing systems with targets are computationally

complete. Inform. Processing Letters, 59 (1996), 129–133.

[248] Gh. P˘aun. DNA computing; Distributed splicing systems.

Structures in Logic and Computer Science. A Selection of Essays in

Honor of A. Ehrenfeucht (J. Mycielski, G. Rozenberg, A. Salomaa,

eds.), Lect. Notes Computer Sci. 1261, Springer, Berlin, 1997, 351–

370.

[249] Gh. P˘aun. Marcus Contextual Grammars. Boston: Kluwer, 1997.

[250] Gh. P˘aun. Controlled H systems and Chomsky h ierarchy.

Fundamenta Informaticae, 30 (1997), 45–57.

[251] Gh. P˘aun. Two-level distributed H systems. Proc. 3rd Conf.

Developments in Language Theory, Thessaloniki, 1997 (S.

Bozapalidis, ed.), Aristotle Univ. of Thessaloniki, 1997, 309–327.

[252] Gh. P˘aun. DNA computing based on splicing: universality results.

Proc. 2nd Intern. Colloq. Universal Machines and Computations,

Metz, 1998, Vol. I, 67–91.

[253] Gh. P˘aun. Distributed architectures in DNA computing based on

splicing: Limiting the size of components. [UMC1], 323–335

[254] Gh. P˘aun. (DNA) Computing by carving. Soft Computing, 3

(1999), 30–36.

[255] Gh. P˘aun, Membrane Computing. An Introduction. Berlin:

Springer, 2002.

[256] Gh. P˘aun, G. Rozenberg. Sticker systems. Theoretical Computer

Sci., 204 (1998), 183–203.

[257] Gh. P˘aun, G. Rozenberg, A. Salomaa. Res tricted use of the splicing

operation. Intern. J. Computer Math., 60 (1996), 17–32.

[258] Gh. P˘aun, G. Rozenberg, A. Salomaa. Computing by splicing.

Theoretical Computer Sci., 168, 2 (1996), 321–336.

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

[259] Gh. P˘aun, G. Rozenberg, A. Salomaa. Computing by splicing.

Programmed and evolving splicing systems. [EC97], 273–277.

[260] Gh. P˘aun, A. Salomaa. Thin and slender languages. Discrete Appl.

Math., 61 (1995), 257–270.

[261] Gh. P˘aun, A. Salomaa. From DNA recombination to DNA

computing. [GCB], 210–220.

[262] Gh. P˘aun, A. Salomaa. DNA computing based on the splicing

operation. Mathematica Japonica, 43 (1996), 607–632.

[263] Gh. P˘aun, L. Sˆantean. Parallel communicating grammar systems:

the regular case. Ann. Univ. Buc., Series Matem.-Inform., 38

(1989), 55–63.

[264] R. Penchovsky, J. S. McCaskill. Cascadable hybridisation transfer

of speciﬁc DNA between microreactor selection modules. [DNA7],

46–56.

[265] M. Penttonen. One-sided and two-side d contexts in formal

grammars. Inform. Control, 25 (1974), 371–392.

[266] M. J. P´erez-Jim´enez, F. Sancho-Caparrini. Solving Knapsack

problems in a sticker based model. [DNA7], 161–171.

[267] M. C. Pirrung, et al. The arrayed primer extension method for

DNA microchip analysis. Molecular computation of satisfaction

problems. J. Am. Chem. Soc., 122 (2000), 1873.

[268] N. Pisanti. DNA computing: a survey. Bull. EATCS, 64 (1998),

188–216.

[269] D. Pixton. Regular splicing systems, manuscript, 1995.

[270] D. Pixton. Linear and circular splicing systems. [INBS], 181–188.

[271] D. Pixton. Regularity of splicing languages. Discrete Appl. Math.,

69 (1996), 101–124.

[272] D. Pixton. Splicing in abstract families of languages. Technical

Report of SUNY Univ. at Binghamton, New York, 1997.

[273] L. Priese. A note on nondeterministic reversible computations.

Technical Report 26/97, Univ. Koblenz-Landau, Institut f¨ur

Informatik, 1997.

[274] L. Priese, Y. Rogozhin, M. Margenstern. Finite H systems with 3

tubes are not predictable. [PCB3], 547–558.

[275] P. Pudlak. Complexity theory and genetics. Proc. 9th Conf. on

Structure in Complexity Theory, 1994, 183–195.

[276] G. Rahonis. Splicing on trees: the iterated case. J. Universal

Computer Sci., 5 (1999), 599–609.

[277] J. H. Reif. Local parallel biomolecular computation. [DNA3], 243–

264.

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

[278] J. H. Reif. Paradigms for biomolecular computation. [UMC1], 72–

93.

[279] J. H. Reif. The emerging discipline of biomolecular computing in

US. New Generation Computing, 20 (2002), 217–236.

[280] J. H. Reif, et al. Experimental construction of very large scale DNA

databases with associative search capability. [DNA6], 231–247.

[281] J. H. Reif, Th. H. LaBean. Computationally inspired

biotechnologies: Improved DNA synthesis and associative search

using error-correcting codes and vector-quantization. [DNA6],

145–172.

[282] J. H. Reif, Th. H. LaBean, N. C. Seeman. Challenges and

applications for self-assembled DNA nanostructures. [DNA6], 173–

198

[283] M. P. Robertson, A. D. Ellington. New directions in nucleic acid

computing: Selected robozymes that can implement re-write rules.

[DNA3], 69–73.

[284] Y. Rogozhin. Small universal Turing machines. Theoretical

Computer Sci., 168 (1996), 215–240.

[285] J. A. Rose, R. J. Deaton. The ﬁdelity of annealing-ligation: A

theoretical analysis. [DNA6], 231–246.

[286] J. A. Rose, R. J. Deaton, M. Hagiya, A. Suyama. PNA-mediated

whiplash PCR. [DNA7], 104–116.

[287] J. A. Rose, R. J. Deaton, M. Hagiya, A. Suyama. The ﬁdelity of

the tag-antitag system. [DNA7], 138–149.

[288] A. L. Rosenberg. On multihead ﬁnite automata. IBM J. R. and

D., 10 (1966), 388–394.

[289] P. W. K. Rothemund. A DNA and restriction enzyme

implementation of Turing machines. [DNA1], 75–120

[290] B. Rovan. A framework for studying grammars. Proc. MFCS’81

(Lect. Notes Computer Sci., 118), Berlin: Springer, 1981, 473–482.

[291] S. Roweis, et al. A sticker based architecture for DNA computation.

[DNA2], 1–27, см. также J. Computational Biology, 5 (1998) 615–

629.

[292] G. Rozenberg, A. Salomaa. The Mathematical Theory of L

Systems. New York: Academic Press, 1980.

[293] G. Rozenberg, A. Salomaa. Cornerstones of Undecidability. New

York: Prentice Hall, 1994.

[294] G. Rozenberg, A. Salomaa. Watson-Crick complementarity,

universal computations and genetic engineering. Techn. Report 96-

28, Dept. Computer Science, Leiden Univ., 1996.

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

[295] Q. Quyang, P. D. Kaplan, L. Shumao, A. Libchaber. DNA solution

of the maximal clique problem. Science, 278 (1997), 446–449.

[296] Y. Sakakibara. Population computation and majority inference in

test tube. [DNA7], 82–91.

[297] Y. Sakakibara, C. Ferretti. Splicing on tree-like structures. [DNA3],

1997, 348–358

[298] Y. Sakakibara, T. Hohs aka. In vitro translation-based

computations. [DNA9], 197–202.

[299] Y. Sakakibara, H. Imai. A DNA-based compu tational model using

a speciﬁc type of restriction enzyme. [DNA8], 315–325.

[300] K. Sakamoto, et al. State transitions by molecules. BioSystems 52

(1999), 81–91.

[301] K. Sakamoto, et al. Molecular computation by DNA hairpin

formation. Science, 288 (2000), 1223–1226.

[302] A. Salomaa. Theory of Automata. Oxford: Pergamon, 1969.

[303] A. S alomaa. On the index of context-free grammars and languages.

Inform. Control, 14 (1969), 474–477.

[304] A. Salomaa. Formal Languages. New York: Academic Press, 1973.

[305] A. Salomaa. Computation and Automata. Cambridge: Cambridge

Univ. Press, 1985.

[306] A. Salomaa. Equality sets for homomorphisms of free monoids.

Acta Cybernetica, 4 (1978), 127–139.

[307] A. Salomaa. Jewels of Formal Language Theory. Rockville:

Computer Science Press, 1981 [Русский перевод: А. Саломаа.

Жемчужины теории формальных языков. М.: Мир, 1986].

[308] A. Salomaa. Public-Key Cryptography. 2nd enlarged edition,

Berlin: Springer, 1996 [Русский перевод 1-го издания: А. Сало-

маа. Криптография с открытым ключом. М.: Мир, 1996].

[309] A. Salomaa. Turing, Watson–Crick, and Lindenmayer. Aspects of

DNA complementarity. [UMC1], 94–107.

[310] M. Sakthi Balan, K. Krithivasan, Y. Sivasubrmanyam: Peptide

computing — universality and complexity. [DNA7], 290–299.

[311] M. P. Sch¨utzenberger. On ﬁnite monoids having only trivial

subgroups. Inform. Control, 8 (1965), 190–194.

[312] D. B. Searls. The linguistics of DNA. American Scientist, 80 (1992),

579–591.

[313] C. E. Shannon. A universal Turing machine with two internal

states. Automata Studies, Annals of Mathematical Studies, 34,

Princeton Univ. Press, 1956, 157–165.

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

[314] R. Siromoney, K. G. Subramanian, V. R. Dare. Circular DNA and

splicing systems. Parallel Image Analysis, Lect. Notes Computer

Sci. 654, Springer, Berlin, 1992, 260–273.

[315] W. Smith. DNA computers in vitro and in vivo. [DNA1], 121–186.

[316] W. M. Sofer. Int roduction to Genetic Engineering. Boston:

Butterworth–Heinemann, 1991.

[317] C. C. Squier. Semicontextual grammars: an example. Bull. Math.

Soc. Sci. Math. Roumanie, 32(80) (1988), 167–170.

[318] Y. Takada, R. Siromoney. On identifying DNA splicing systems

from examples. Proc. AII’92, Lect. Notes in AI, 642, Berlin:

Springer, 1992, 305–319.

[319] A. Takahara, T. Yokomori. On the computational powers of

insertion-deletion systems. [DNA8], 269–280.

[320] Y. Takenaka, A. Hashimoto. Shortening the computational time of

the ﬂuorescent DNA computing. [DNA8], 85–94.

[321] F. Tanaka, et al. Developing support system for sequence design

in DNA computing. [DNA7], 129–137.

[322] P. Turakainen. A uniﬁed approach to characterizations of

recursively enumerable languages. Bull. EATCS, 45 (1991), 223–

228.

[323] A. M. Turing. On computable numbers, with an application to the

Entscheidungsproblem. Proc. London Math. Soc., Ser. 2, 42 (1936),

230–265; a correction, 43 (1936), 544–546.

[324] A. M. Turing. Computing machinery and intelligence. Mind, 59

(1950), 433–460.

[325] H. Uej ima, M. Hagiya. Secondary structure design of multi-state

DNA machines based on sequential s tructure transitions. [DNA9],

74–85.

[326] H. Uejima, M. Hagiya, S. Kobayashi. Horn clause computation by

self-assembly of DNA molecules. [DNA7], 308–320.

[327] D. van Noort, F.-U. Gast, J. S. McCaskill. DNA computing in

microreactors. [DNA7], 33–45.

[328] D. van Noort, L. F. Landweber. Towards a re-programmable DNA

computer. [DNA9], 190–197.

[329] K. Wakabayashi, M. Yamamura. A realization of information gate

by using Enterococcus faec alis pheromone system. [DNA7], 269–

278.

[330] M. R. Walker, R. Rapley. Route Maps in Gene Technology. Oxford:

Blackwell Science, 1997.

[331] L. Wang, et al. Multiple word DNA computing on surfaces. J. Am.

Chem. Soc., 122 (2000), 7435–7440.

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

[332] P. W¸asiewicz, et al. DNA computing: Implementation of data

ﬂow logical operations. Future Generation Computer Systems, 17

(2001), 361–378.

[333] P. W¸asiewicz, J. J. Mulawka. Molecular genetic programming. Soft

Computing, 5 (2001), 106–113.

[334] E. Winfree. Comp lexity of restricted and unrestricted models of

molecular computability. [DNA1], 187–198.

[335] E. Winfree. On the computational power of DNA annealing and

ligation. [DNA1], 199–210.

[336] E. Winfree, T. Eng, G. Rozenberg. String tile mo d els for DNA

computing by self-assembly. [DNA6], 63–88

[337] E. Winf ree, X. Yang, N. Seeman. Universal computation via self -

assembly of DNA; some theory and experiments. [DNA2], 172–

190.

[338] D. Wood . Iterated a-NGSM maps and Γ-systems. Inform. Control,

32 (1976), 1–26.

[339] D. Wood. Theory of Computation. New York: Harper and Row,

1987.

[340] D. H. Wood, et al. In vitro selection for a OneMax DNA

evolutionary computation. [DNA5], 23–38.

[341] D. H. Wood, et al. DNA starts to learn poker. [DNA7], 92–103.

[342] D. H. Wood, C. L. Taylor Clelland, C. Bancroft. Universal biochip

readout of directed hamiltonian path problems. [DNA8], 168–181.

[343] M. Yamamoto, et al. A study on the hybridization process in DNA

computing. [DNA5], 101–110.

[344] M. Yamamoto, et al. Solutions of shortest path problems by

concentration control. [DNA7], 203–212.

[345] M. Yamamoto, Y. Hiroto, T. Motoba. Another realization of

aqueous computing with peptide nucleic acid. [DNA7], 213–222.

[346] T. Yoichi, H. Akihiro. A proposal of DNA computing on beads

with application to SAT problems. [DNA7], 182–190.

[347] T. Yokomori. YAC: Yet another computation model of self-

assembly. [DNA5], 153–168.

[348] T. Yokomori. Molecular computing paradigm – toward freedom

from Turing’s charm. Natural Computing, 1 (2002), 333–390.

[349] T. Yokomori, M. Ishida, S. Kobayashi. Learning local languages

and its application to protein α-chain identiﬁcation. Proc. 27th

Hawaii Intern. Conf. System Sci., Vol. V, 1994, 113–122.

[350] T. Yokomori, S. Kobayashi. DNA evolutionary linguistics and RNA

structure modeling: a computational approach. [INBS], 38–45.

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

[351] T. Yokomori, S. Kobayashi. DNA-EC: A model of DNA computing

based on equality checking. [DNA3], 334–347.

[352] T. Yokomori, S. Kobayashi, C. Ferretti. On the power of circular

splicing systems and DNA computability. [EC97], 219–224.

[353] T. Yokomori, Y. Sakakibara, S. Kobayashi. A magic pot: self-

assembly computation revised. [FNC], 418–429.

[354] H. Yoshida, A. Suyama. Solution to 3-SAT by breadth ﬁrst search.

[DNA3], 9–22.

[355] C. Zandron, C. Ferretti, G. Mauri. A reduced distributed splicing

system for RE languages. New Trends in Formal Languages.

Control, Cooperation, Combinatorics (Gh. P˘aun, A. Salomaa,

eds.), Lect. Notes Computer Sci. 1218, Berlin: Springer, 1997, 346–

366.

[356] C. Zandron, G. Mauri, C. Ferretti, P. Bonizzoni. Splicing systems

using merge and separate operations. [MCLB], 435–446.

[357] K.-H. Zimmermann. On applying molecular computation to binary

linear codes. IEEE Trans. on Inform. Theory, 48 (2002) 505–509.

518 Глоссарий

Глоссарий биохимических терминов

In vitro — вне живого организма, в пробирке.

In vivo — в живом объекте.

Агарозный гель — гель, образованный из продуктов частичного

гидролиза крахмала.

Аденин — азотистое основание из группы пуринов.

Азотистое основание — гетероцикли чес кое химическое соедине-

ние, составная часть нуклеотидов.

Водородная связь — слабая химическая связь, возникающая за

счет притяжения электроотрицательного атома кислорода одной

гидроксильной группы с электроположительным атомом водоро-

да другой гидроксильной группы.

Гель-электрофорез — вид электрофореза, при котором в качестве

носителя, в котором происходит разделение молекул, использу-

ются гели.

Гибридизация — создание гибрид ов, в м олек улярной биологии —

создание гибридных молекул, например, гибридных ДНК.

Гуанин — азотистое основание из группы пуринов.

Дезоксирибонуклеиновая кислота (ДНК) — биополимер, мо-

номерами которого являются дезоксирибонуклеотиды.

Дезоксирибонуклеотид — мономе р ДНК, состоящий из азоти-

стого основания, сахара (дезоксирибозы) и фосфатной группы.

Денатурация — нарушение структуры биополимеров, в частности,

нарушение структуры ДНК, ее разделение н а одиночные цепи.

Дидезоксиферментный метод — метод секвенирования ДНК с

использованием модифицированных нуклеотидов — дидезокси-

нуклеотидов, предложен Ф. Сэнгером в 1975 г.

ДНК-нуклеаза — фермент, расщепляющий ДНК.

Ковалентная связь — прочная химическая связь, при которой

электроны взаимодействующих атомов образуют единое элек-

тронное облако, в большей или меньшей степени смещенн ое в

отношении одного атома.

Глоссарий 519

Комплементарность — свойство соответствия пуриновых нуклео-

тидов пиримидиновым, их способность образовывать водородные

связи между собой.

Лигаза — фермент, осуществляющий сшивание молекулы ДНК,

устранение насечек.

Липкие концы — выступающие одноцепочечные концы молекулы

ДНК, образовавшиеся в результате действия рестриктаз.

Метод Сэнгера — см. дидезоксиферментный метод.

Модифицирующий фермент — фермент, изменяющий химиче-

скую структуру ДНК, присоединяющий или удаляющий хими-

ческие группы.

Молекула-зонд — молекула, комплементарная молекуле-мише-

ни.

Молекула-мишень — определенная молекула, в отношении кото-

рой производятся некоторые действия.

Насечка — зазор между соседними нуклеотидами в цепи ДНК, от-

сутствие фосфодиэфирной связи между ними .

Нуклеотид — химическое соединение, образованное присоединени-

ем пятиуглеродного сахара (рибозы или дезоксирибозы) и фос-

фатной группы к азотистому основанию.

Олигонуклеотид — короткая (состоящая из нескольких нуклео-

тидов), одноцепочечная молекула, синтезированная химическим

путем.

Пиримидины — группа азотистых оснований (гуанин, цитозин

и др.).

Полиакриламидный гель — гел ь, образованный из акриламида

и его производного метиленбисакриламида с добавлением «сши-

вающих» агентов.

Полимераза — фермент, осуществляющий реакции полимериза-

ции, т. е. синтеза полимеров из мономеров.

Полимеразная цепная реакция (ПЦР) — метод получения ко-

пий исходной молекулы ДНК или ее фрагментов.

Праймер — затравка, фрагмент нуклеиновой кислоты, необходи-

мый для действия фермента полимеразы, состоит из нескольких

последовательно связанных друг с другом нуклеотидов.

Праймирование — образование праймера на молекуле ДНК.

Пурины – группа азотистых оснований (аденин, тимин, урацил и

др.).

520 Глоссарий

Ренатурация — восстановление структуры биополимеров, в част-

ности, восстановление структуры ДНК в виде двойной спирали.

Рестриктаза — эндонуклеаза, расщепляющая только двуцепочеч-

ные ДНК в строго определенном месте.

Рибоза — пятиуглеродный сахар.

Рибонуклеиновая кислота (РНК) — биополимер, мономерами

которого являются рибонуклеотиды.

Рибонуклеотид — нуклеотид, в состав которого входит сахар ри-

боза.

Сайт узнавания — место связывания фермента рестриктазы.

Сахар — растворимый углевод.

Секвенирование — установление последовательности нуклеоти-

дов в молекуле биополимера, в частности, ДНК.

Сшивание — образование фосфодиэфирных связей между соседни-

ми нуклеотидами в молекуле ДНК, в частности, з акрыти е на-

сечки.

Тимин — азотистое основание из группы пиримидинов.

Урацил — азотистое основание из группы пиримидинов.

Фермент — биологический катализатор белковой природы.

Фосфатная группа — остаток фосфорной кислоты.

Фосфодиэфирная связь — ковалентная связь, образующаяся

между фосфатной группой одного нуклеотида и гидроксильной

группой другого.

Цитозин — азотистое основание из группы пиримидинов.

Экзонуклеаза — фермент, расщепляющий ДНК путем удаления

нуклеотидов с конца молекулы.

Электрофорез — метод разделения смеси молекул при их движе-

нии в электрическом поле.

Эндонуклеаза — фермент, расщепляющий внутренние фосфоди-

эфирные связи молекулы ДНК.