标签: pattern-matching

我正在使用长度为25的DNA序列(参见下面的例子).我有一个230,000的清单,需要寻找整个基因组中的每个序列(弓形虫寄生虫).我不确定基因组有多大,但比230,000个序列长得多.

我需要查找每个25个字符的序列,例如,(AGCCTCCCATGATTGAACAGATCAT).

基因组被格式化为连续的字符串,即(CATGGGAGGCTTGCGGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTTGCGGAGTGCGGAGCCTGAGCCTGAGGGCGGAGCCTGAGGTGGGAGGCTT ....)

我不关心它被发现的地点和次数,只关注它是否存在.
我认为这很简单 -

str.find(AGCCTCCCATGATTGAACAGATCAT)

但我还要找到在任何位置定义为错误(不匹配)的近距离匹配,但只有一个位置,并记录序列中的位置.我不知道怎么做到这一点.我唯一能想到的是使用通配符并在每个位置使用通配符执行搜索.即,搜索25次.

例如,
AGCCTCCCATGATTGAACAGATCAT
AGCCTCCCATGATAGAACAGATCAT

与位置13处的不匹配密切匹配.

速度不是一个大问题,因为我只做了3次,但如果它很快就会很好.

有些程序可以执行此操作 - 查找匹配项和部分匹配项 - 但我正在寻找一种使用这些应用程序无法发现的部分匹配项.

这是perl的类似帖子,虽然它们只是比较序列而不是搜索连续的字符串:

相关文章

我刚刚在一些代码中发现了一个我没写过的错误,我有点惊讶:

Pattern pattern = Pattern.compile("\\d{1,2}.\\d{1,2}.\\d{4}");
Matcher matcher = pattern.matcher(s);

尽管这个代码在输入数据上严重失败,但我们得到了(因为它试图找到17.01.2011格式的日期并找回10396/2011之类的内容然后崩溃,因为它无法解析日期,但实际上是 'a'这个问题的重点;)我想知道:

• 不是点之一Pattern.compile是一个速度优化(由预编译正则表达式)？

• 不应该将所有"静态"模式总是编译成静态模式吗？

在网络上有很多例子,使用Pattern.compile总是重新编译相同的模式,我开始怀疑我是否看到了东西.

不是(假设字符串是静态的,因此不是动态构造的):

static Pattern pattern = Pattern.compile("\\d{1,2}.\\d{1,2}.\\d{4}");

总是优先于非静态模式参考？

我目前正在学习模式匹配算法,并且遇到了这两种算法.我有以下一般想法:

KMP

• 从左到右比较文本
• 使用故障数组智能地转换
• 取O(m),其中m是模式的长度,以计算故障数组
• 需要O(m),空间
• 需要O(n),时间来搜索字符串

BM

• 比较最后一个字符的模式
• 使用糟糕的角色跳跃和良好的后缀跳跃
• 采用O(m +字母表大小)来计算表格
• 取O(m +字母大小),空格
• 需要O(n),但通常更好搜索

我遇到了以下引发这个问题的问题(正确还是错误):

如果我们想要在许多不同的文本中重复搜索相同的模式,那么Knuth-Morris-Pratt(KMP)算法是一个很好的选择.

所以我认为答案是正确的,因为假设每次在不同文本上运行算法时,预处理只是O(n),对于BM,它是O(n +字母表大小).但是,我不确定我是否正在做出正确的假设,即每次重新运行算法时都会重新计算新表.因为说文字总是落在英文字母表中.我只需要计算一次表,只需重用表.那么在一天结束的时候,这个问题的答案是否依赖于这样的事实:算法都是在包含在同一字母表中的文本上运行,还是有一些其他可能影响它的因素？

我只是想知道是否可以使用函数式编程语言(Haskell/F#/ Caml)的模式匹配工具多次匹配相同的值.

试想下面的例子:

plus a a = 2 * a
plus a b = a + b

当使用两个相似的值(将存储在其中a)调用函数时,将调用第一个变体.

一个更有用的应用程序就是这个(简化AST).

simplify (Add a a) = Mult 2 a

但是Haskell拒绝这些代码并警告我有相互矛盾的定义a - 我必须做明确的case/if-checks而不是找出函数是否具有相同的值.是否有任何技巧可以表明我想要匹配的变量会多次出现？

我正在实现一个Swing组件,我想要克服#### untypedness Reactor.所以我认为这会奏效:

trait Foo[A] extends scala.swing.Publisher {
  final case class Bar(parent: Vector[A], children: A*) extends scala.swing.event.Event
}

trait Test {
  val foo: Foo[Int]

  foo.reactions += {
    case foo.Bar(parent, children) => {
      println(parent.sum - children)
    }
  }
}

不幸的是,这给了我两个编译器警告:

The outer reference in this type test cannot be checked at run time.
  final case class Bar(parent: Vector[A], children: A*) extends scala.swing.event.Event
                   ^
The outer reference in this type test cannot be checked at run time.
    case foo.Bar(parent, children) => …

现在,我有一些基本上像这样的代码:

data Expression 
    = Literal Bool 
    | Variable String
    | Not Expression 
    | Or Expression Expression 
    | And Expression Expression
    deriving Eq

simplify :: Expression -> Expression
simplify (Literal b) = Literal b
simplify (Variable s) = Variable s
simplify (Not e) = case simplify e of
    (Literal b) -> Literal (not b)
    e'          -> Not e'
simplify (And a b) = case (simplify a, simplify b) of
    (Literal False, _) -> Literal False
    (_, Literal False) -> Literal False …

我最近偶然发现了D编程语言,我非常喜欢它.你可以编程真正的高级别,同时拥有完整的硬件访问,如在C.

来自一个相当功能性的背景(Haskell,scala)我正在寻找D模式匹配的方法,但我在http://www.digitalmars.com/d/上找不到任何东西.在Haskell中,语言本身支持模式匹配.在Scala中,它通过case类或提取器(具有unapply方法的普通对象)实现.

可以在D中执行此操作吗？

std.concurrency中的receive方法用于在actor类式中进行并发,就像在erlang和scala中一样,在这些方法上采用了大量的函数和模式数学.但我认为它不像其他语言那样灵活.你能用卫兵吗？你能在scala中提取Object的内容吗？

我想看看,如果"001"还是"100"还是"000"在4个字符的字符串发生0和1.例如,4个字符的字符串可以是"1100"或"0010"或"1001"或"1111".如何使用单个命令匹配字符串中的许多字符串？

我知道grep可以用于模式匹配,但是使用grep,我一次只能检查一个字符串.我想知道多个字符串是否可以与其他命令一起使用或者与grep本身一起使用.

只是盯着使用Haskell并实现(据我所知),没有直接的方法来检查字符串,看它是否包含一个较小的字符串.所以我想我只是试一试.

基本上,我们的想法是检查两个字符串是否大小相同并且相等.如果检查的字符串较长,则递归地删除头部并再次运行检查,直到检查的字符串长度相同.

其余的可能性我使用模式匹配来处理它们.这就是我想出的:

stringExists "" wordToCheckAgainst = False
stringExists wordToCheckFor "" = False
stringExists wordToCheckFor wordToCheckAgainst | length wordToCheckAgainst < length wordToCheckFor = False
                                               | length wordToCheckAgainst == length wordToCheckFor = wordToCheckAgainst == wordToCheckFor
                                               | take (length wordToCheckFor) wordToCheckAgainst == wordToCheckFor = True
                                               | otherwise = stringExists wordToCheckFor (tail wordToCheckAgainst)

我有一组潜在的无限符号:A, B, C, ...还有一个独特的特殊占位符?(其含义将在下面解释).

考虑非空有限树,使得每个节点都附有符号和0或更多非空子树.给定节点的子树的顺序是重要的(因此,例如,如果存在具有2个子树的节点,则我们可以区分哪一个留下,哪一个是正确的).任何给定的符号都可以出现在连接到不同节点的树0中.占位符符号?只能附加到叶节点(即没有子树的节点).根据树的通常定义,树是非循环的.

有限性要求意味着树中的节点总数是正有限整数.由此得出,每个子树中附加符号的总数,树深度和节点总数都是有限的.

树以功能表示法给出:节点由附加到其上的符号表示,如果有任何子树,则后面是括号,其中包含以相同方式递归表示的以逗号分隔的子树列表.所以,例如树

                    A
                   / \
                  ?   B
                     / \
                    A   C
                   /|\
                  A C Q
                       \
                        ?

表示为A(?,B(A(A,C,Q(?)),C)).

我有一个预先计算的一组不变的树S,它们将被用作匹配的模式.该集合通常具有~10 ^5个树,并且其每个元素通常具有~10-30个节点.我可以利用足够的时间事先创建最适合我下面所述问题的S表示.

我需要编写一个接受树T(通常有~10 ^2个节点)的函数,并且如果T包含任何S元素作为子树,则尽可能快地检查,前提是任何带有占位符符号的节点都?匹配任何非空子树(当它出现在T或S)的元素中时.

请建议存储集合S的数据结构和检查匹配的算法.任何编程语言或伪代码都可以.