在 Prolog DCG 中，如何去除过通解？

Question

我有一个包含序列的文本文件。例如：

GGGGGGGGAACCCCCCCCCCTTGGGGGGGGGGGGGGGGAACCCCCCCCCCTTGGGGGGGG

我已经写了下面的DCG来找到AA和TT之间的序列。

:- use_module(library(pio)).
:- use_module(library(dcg/basics)).
:- portray_text(true).

process(Xs) :- phrase_from_file(find(Xs), 'string.txt').

anyseq([]) -->[].
anyseq([E|Es]) --> [E], anyseq(Es).

begin --> "AA".
end -->"TT".

find(Seq) -->
     anyseq(_),begin,anyseq(Seq),end, anyseq(_).

我查询并得到：

?- process(Xs).
 Xs = "CCCCCCCCCC" ;
 Xs = "CCCCCCCCCCTTGGGGGGGGGGGGG...CCCCC" ;
 Xs = "CCCCCCCCCC" ;
false.

但我不希望它找到第二个解决方案或类似的解决方案。只有一对 AA 和 TT 之间的解决方案不是所有组合。我有一种感觉，我可以在库 dcg basiscs 中使用 string_without 和 string，但我不明白如何使用它们。

Answer 1

您的 anyseq//1 与库 (dcg/basics) 中的字符串//1 相同，并且共享相同的 'problem'.

为了保持控制，我会引入一个 'between separators' 状态：

elem(E) --> begin, string(E), end, !.

begin --> "AA".
end -->"TT".

find(Seq) -->
     anyseq(_),elem(Seq).

anyseq([]) -->[].
anyseq([E|Es]) --> [E], anyseq(Es).

process(Xs) :-
   phrase(find(Xs), `GGGGGGGGAACCCCCCCCCCTTGGGGGGGGGGGGGGGGAACCCCC+++CCCCCTTGGGGGGGG`,_).

现在我明白了

?- process(X).
X = "CCCCCCCCCC" ;
X = "CCCCC+++CCCCC" ;
false.

注意匿名变量作为 phrase/3 的最后一个参数：需要它来适应 'control flow' 中由使用的更严格的模式引起的变化：elem//1 is not 后接anyseq//1，因为任意两个序列'sharing' anyseq//1 都会有问题。

最后，您应该将语法更改为使用正确的递归语法收集元素//1....

Answer 2

首先，我建议您最有可能曲解问题，至少如果这是关于 mRNA 序列的。在那里，碱基出现在三联体或密码子中，开始是甲硫氨酸或甲硫氨酸，但末端是三个不同的三联体。所以很可能你想使用这样的表示。

中间的序列可以使用 all_seq//2, if_/3、(=)/3:

定义

mRNAseq(Cs) -->
   [methionine],
   all_seq(\C^maplist(dif(C),[amber,ochre,opal]), Cs),
   ( [amber] | [ochre] | [opal]).

或：

mRNAseq(Cs) -->
   [methionine],
   all_seq(list_without([amber,ochre,opal]), Cs),
   ( [amber] | [ochre] | [opal]).

list_without(Xs, E) :-
   maplist(dif(E), Xs).

但是回到你的字面陈述，以及你关于声明性名称的问题。 anyseq和seq意思基本一样

% :- set_prolog_flag(double_quotes, codes).   % pick this
:- set_prolog_flag(double_quotes, chars).     % or pick that

... --> [] | [_], ... .

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

mRNAcontent(Cs) -->
   ...,
   "AA",
   seq(Cs),
   "TT",
   {no_TT(Cs)},  % restriction
   ... .

no_TT([]).
no_TT([E|Es0]) :-
   if([E] = "T",
      ( Es0 = [F|Es], dif([F],"T") ),
      Es0 = Es),
   no_TT(Es).

no_TT/1的意思是：列表中没有序列"TT"，也没有"T"结尾。所以 no_TT("T") 也失败了，因为它可能与随后的 "TT"!

发生冲突

那么为什么使用纯粹、单调的定义是个好主意？您很可能会想要添加限制。在纯单调形式中，限制是无害的。但是在另一个答案中建议的程序版本中，您会得到完全不同的结果，完全没有限制。

在 Prolog DCG 中，如何去除过通解？

In Prolog DCGs, how to remove over general solutions?

prolog

swi-prolog

dcg