在 Prolog DCG 中,如何去除过通解?
In Prolog DCGs, how to remove over general solutions?
我有一个包含序列的文本文件。例如:
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
,但我不明白如何使用它们。
您的 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....
首先,我建议您最有可能曲解问题,至少如果这是关于 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"
!
发生冲突
那么为什么使用纯粹、单调的定义是个好主意?您很可能会想要添加限制。在纯单调形式中,限制是无害的。但是在另一个答案中建议的程序版本中,您会得到完全不同的结果,完全没有限制。
我有一个包含序列的文本文件。例如:
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
,但我不明白如何使用它们。
您的 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....
首先,我建议您最有可能曲解问题,至少如果这是关于 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"
!
那么为什么使用纯粹、单调的定义是个好主意?您很可能会想要添加限制。在纯单调形式中,限制是无害的。但是在另一个答案中建议的程序版本中,您会得到完全不同的结果,完全没有限制。