时间戳

首页 > 解决方案 > 使用“库（聚合）”计算两个序列中匹配元素的复杂性

prolog - 使用“库（聚合）”计算两个序列中匹配元素的复杂性

问题描述

我们想计算恰好代表 DNA 序列的两个（可能很长）字符串之间的对应关系。这些序列是从 char 中获取的字符列表，其中a,c,t,g,'_''_' 是一个“不知道”的占位符，它从不对应于任何东西，甚至它本身。在这种情况下，我们使用library(aggregate)（感谢 CapelliC 的想法）：

match(Seq1,Seq2,Count) :-
   aggregate_all(count,
      (
         nth1(Pos,Seq1,X),
         nth1(Pos,Seq2,X),
         memberchk(X,[a,c,g,t])
      ),
      N).

这种方法可以与“直截了当”的方法进行比较，在这种方法中，人们将建立一个（尾递归）递归，该递归只是串联地遍历两个序列并成对地比较元素，同时计数。

由于序列可能非常大，因此算法复杂性变得有趣。

可以预期，n = length(sequence)并且两个序列的长度相同：

上述算法的（时间和空间）复杂度是多少，为什么？

测试代码

为了补充上述内容，基于 SWI-Prolog 的plunit测试代码块：

:- begin_tests(atcg).

wrap_match(String1,String2,Count) :-
   atom_chars(String1,Seq1),
   atom_chars(String2,Seq2),
   fit(Seq1,Seq1,0,Count).

test("string 1 empty",nondet) :-
   wrap_match("atcg","",Count), 
   assertion(Count == 0).
      
test("string 2 empty") :-
   wrap_match("","atcg",Count), 
   assertion(Count == 0).

test("both strings empty") :-
   wrap_match("","",Count), 
   assertion(Count == 0).

test("both strings match, 1 char only") :-
   wrap_match("a","a",Count),   
   assertion(Count == 1).

test("both strings match") :-
   wrap_match("atcgatcgatcg","atcgatcgatcg",Count),   
   assertion(MatchCount == 12).

test("both strings match with underscores") :-
   wrap_match("_TC_ATCG_TCG","_TC_ATCG_TCG",Count),   
   assertion(MatchCount == 9).

test("various mismatches 1") :-
   wrap_match("atcgatcgatcg","atcgatcgatcg",Count),   
   assertion(MatchCount == 8).

test("various mismatches with underscores") :-
   wrap_match("at_ga_cg__cg","atcgatcgatcg",Count),   
   assertion(Count == 8).
   
:- end_tests(atcg).

所以：

?- run_tests.
% PL-Unit: atcg ........ done
% All 8 tests passed
true.

标签： prologtime-complexity

解决方案

经验信息

在使用下面的代码进行一些手动数据收集（需要自动化的东西）之后，它会输出经过的时间和对控制台进行的推理次数：

gimme_random_sequence(Length,Seq) :-
   length(Seq,Length),
   maplist(
      [E]>>(random_between(0,3,Ix),nth0(Ix,[a,t,c,g],E)),
      Seq).
           
how_fast(Length) :-
   gimme_random_sequence(Length,Seq1),
   gimme_random_sequence(Length,Seq2),
   time(match(Seq1,Seq2,_)).

...以及 LibreOffice Calc 中的一些图形摸索（我的ggplot技能生疏），我们有经验数据表明该算法的成本是

O（（长度（序列））²）。

算法复杂度

Count,Inferences,Seconds,milliseconds,megainferences
1000,171179,0.039,39,0.171179
2000,675661,0.097,97,0.675661
3000,1513436,0.186,186,1.513436
4000,2684639,0.327,327,2.684639
5000,4189172,0.502,502,4.189172
6000,6027056,0.722,722,6.027056
7000,8198103,1.002,1002,8.198103
8000,10702603,1.304,1304,10.702603
9000,13540531,1.677,1677,13.540531
10000,16711607,2.062,2062,16.711607
11000,20216119,2.449,2449,20.216119
20000,66756619,8.091,8091,66.756619
30000,150134731,17.907,17907,150.134731
40000,266846773,32.012,32012,266.846773
50000,416891749,52.942,52942,416.891749
60000,600269907,74.103,74103,600.269907

推荐阅读