Context-Free Recombinations

Jarkko Kari () and Lila Kari ()
Additional contact information
Jarkko Kari: University of Iowa, Department of Computer Science 15 MLH
Lila Kari: University of Western Ontario, Department of Computer Science

Chapter Chapter 32 in Where Mathematics, Computer Science, Linguistics and Biology Meet, 2001, pp 361-375 from Springer

Abstract: Abstract We address the issue of the computational power of a formal model ([3], [6]) for the guided homologous recombinations that take place during gene rearrangement in ciliates. Results in [7], [5] have shown that a generalization of this model that assumes context-controlled recombinations has universal computational power. Complementing results in [4], [11], [12], [15], we study properties of context-free recombinations and characterize the languages generated by context-free recombination systems. As a corollary, we obtain context-free recombinations which are computationally weak, being able to generate only regular languages. This is one more indicator that, most probably, the presence of direct repeats does not provide all the information needed for accurate splicing during gene rearrangement.

Keywords: Turing Machine; Gene Rearrangement; Regular Language; Finite Automaton; Junction Sequence (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-94-015-9634-3_32

Ordering information: This item can be ordered from
http://www.springer.com/9789401596343

DOI: 10.1007/978-94-015-9634-3_32

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().