寻找核苷酸和氨基酸序列中存在k个差异的比对。

Locating alignments with k differences for nucleotide and amino acid sequences.

作者信息

Landau G M, Vishkin U, Nussinov R

机构信息

Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Israel.

出版信息

Comput Appl Biosci. 1988 Mar;4(1):19-24. doi: 10.1093/bioinformatics/4.1.19.

DOI:10.1093/bioinformatics/4.1.19

PMID:3382993

Abstract

Given two sequences, a pattern of length m, a text of length n and a positive integer k, we give two algorithms. The first finds all occurrences of the pattern in the text as long as these do not differ from each other by more than k differences. It runs in O(nk) time. The second algorithm finds all subsequence alignments between the pattern and the test with at most k differences. This algorithm runs in O(nmk) time, is very simple and easy to program.

摘要

给定两个序列、一个长度为 m 的模式、一个长度为 n 的文本以及一个正整数 k，我们给出两种算法。第一种算法可找到模式在文本中的所有出现位置，前提是这些出现位置彼此之间的差异不超过 k 个。该算法的运行时间为 O(nk)。第二种算法可找到模式与文本之间差异至多为 k 个的所有子序列比对。此算法的运行时间为 O(nmk)，非常简单且易于编程。