کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
462323 696741 2011 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the study of ambiguity and the trade-off between measures and ambiguity in insertion–deletion languages
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
On the study of ambiguity and the trade-off between measures and ambiguity in insertion–deletion languages
چکیده انگلیسی

Gene insertion and deletion are the operations that occur commonly in DNA processing and RNA editing. Based on these operations, a computing model has been formulated in formal language theory known as insertion–deletion systems. In this paper we study about ambiguity issues of these systems. First, we define six levels of ambiguity for insertion–deletion systems that are based on the components used in the derivation such as axiom, contexts and strings  . Next, we show that there are inherently ii-ambiguous insertion–deletion languages which are jj-unambiguous for the combinations (i,j)∈{(5,4),(4,3),(4,2),(3,1),(2,1),(1,0),(0,1)}(i,j)∈{(5,4),(4,3),(4,2),(3,1),(2,1),(1,0),(0,1)}. As an application, we discuss with an example that how some of these ambiguity levels can be interpreted in gene sequences. Further, we prove an important result that the ambiguity problem of insertion–deletion systems is undecidable. Then, we define six new measures for insertion–deletion systems based on used contexts and strings. Finally, we analyze the trade-off between ambiguity levels and measures. We note that there are languages which are inherently ii-ambiguous (for i=5,4,2,0i=5,4,2,0) when a measure MM is minimal for the languages but they are ii-unambiguous otherwise.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Nano Communication Networks - Volume 2, Issues 2–3, June–September 2011, Pages 106–118
نویسندگان
, , , ,