本文目录导读：
我来介绍几种在PHP项目中实现序列匹配的方法,从简单到高级：
基本字符串匹配
精确匹配
<?php
// 简单精确匹配
$text = "ATCGATCGATCG";
$pattern = "ATCG";
if (strpos($text, $pattern) !== false) {
echo "找到匹配";
}
// 获取所有匹配位置
function findAllMatches($text, $pattern) {
$positions = [];
$offset = 0;
while (($pos = strpos($text, $pattern, $offset)) !== false) {
$positions[] = $pos;
$offset = $pos + 1;
}
return $positions;
}
print_r(findAllMatches("ATCGATCGATCG", "ATCG"));
使用正则表达式进行模式匹配
<?php
// 模糊匹配（允许一个差异）
function fuzzyMatch($text, $pattern) {
$pattern = preg_quote($pattern, '/');
// 允许最多一个字符不同
$regex = '/' . implode('.?', str_split($pattern)) . '/';
preg_match_all($regex, $text, $matches, PREG_OFFSET_CAPTURE);
return $matches[0];
}
$text = "ATCGGCTAGC";
$pattern = "ATCG";
$results = fuzzyMatch($text, $pattern);
print_r($results);
实现Smith-Waterman局部比对算法
<?php
class SequenceAligner {
private $matchScore = 2;
private $mismatchPenalty = -1;
private $gapPenalty = -1;
public function align($seq1, $seq2) {
$len1 = strlen($seq1);
$len2 = strlen($seq2);
// 创建得分矩阵
$matrix = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, 0));
$maxScore = 0;
$maxPos = [0, 0];
// 填充矩阵
for ($i = 1; $i <= $len1; $i++) {
for ($j = 1; $j <= $len2; $j++) {
$match = $matrix[$i-1][$j-1] +
($seq1[$i-1] === $seq2[$j-1] ? $this->matchScore : $this->mismatchPenalty);
$delete = $matrix[$i-1][$j] + $this->gapPenalty;
$insert = $matrix[$i][$j-1] + $this->gapPenalty;
$matrix[$i][$j] = max(0, $match, $delete, $insert);
if ($matrix[$i][$j] > $maxScore) {
$maxScore = $matrix[$i][$j];
$maxPos = [$i, $j];
}
}
}
// 回溯找到最佳局部比对
return $this->traceback($matrix, $seq1, $seq2, $maxPos);
}
private function traceback($matrix, $seq1, $seq2, $pos) {
$align1 = '';
$align2 = '';
$i = $pos[0];
$j = $pos[1];
while ($i > 0 && $j > 0 && $matrix[$i][$j] > 0) {
if ($seq1[$i-1] === $seq2[$j-1]) {
$align1 = $seq1[$i-1] . $align1;
$align2 = $seq2[$j-1] . $align2;
$i--; $j--;
} elseif ($matrix[$i][$j] === $matrix[$i-1][$j-1] + $this->mismatchPenalty) {
$align1 = $seq1[$i-1] . $align1;
$align2 = $seq2[$j-1] . $align2;
$i--; $j--;
} elseif ($matrix[$i][$j] === $matrix[$i-1][$j] + $this->gapPenalty) {
$align1 = $seq1[$i-1] . $align1;
$align2 = '-' . $align2;
$i--;
} else {
$align1 = '-' . $align1;
$align2 = $seq2[$j-1] . $align2;
$j--;
}
}
return [
'seq1' => $align1,
'seq2' => $align2,
'score' => $matrix[$pos[0]][$pos[1]]
];
}
}
// 使用示例
$aligner = new SequenceAligner();
$seq1 = "ATCGGCTA";
$seq2 = "ATCGCTTA";
$result = $aligner->align($seq1, $seq2);
echo "序列1: " . $result['seq1'] . "\n";
echo "序列2: " . $result['seq2'] . "\n";
echo "得分: " . $result['score'] . "\n";
使用KMP算法进行高效匹配
<?php
class KMPMatcher {
public function search($text, $pattern) {
$matches = [];
$lps = $this->computeLPS($pattern);
$i = 0; // text索引
$j = 0; // pattern索引
$n = strlen($text);
$m = strlen($pattern);
while ($i < $n) {
if ($pattern[$j] === $text[$i]) {
$i++;
$j++;
}
if ($j === $m) {
$matches[] = $i - $j;
$j = $lps[$j - 1];
} elseif ($i < $n && $pattern[$j] !== $text[$i]) {
if ($j !== 0) {
$j = $lps[$j - 1];
} else {
$i++;
}
}
}
return $matches;
}
private function computeLPS($pattern) {
$m = strlen($pattern);
$lps = array_fill(0, $m, 0);
$len = 0;
$i = 1;
while ($i < $m) {
if ($pattern[$i] === $pattern[$len]) {
$len++;
$lps[$i] = $len;
$i++;
} else {
if ($len !== 0) {
$len = $lps[$len - 1];
} else {
$lps[$i] = 0;
$i++;
}
}
}
return $lps;
}
}
// 使用示例
$matcher = new KMPMatcher();
$text = "ATCGGCTAGCATCG";
$pattern = "ATCG";
$positions = $matcher->search($text, $pattern);
echo "匹配位置: " . implode(", ", $positions) . "\n";
使用Levenshtein距离进行近似匹配
<?php
// 使用PHP内置函数
$text = "ATCG";
$pattern = "ATCG";
// 计算编辑距离
$distance = levenshtein($text, $pattern);
echo "编辑距离: " . $distance . "\n";
// 自定义近似匹配
function approximateMatch($text, $pattern, $maxDistance = 2) {
$matches = [];
$len = strlen($pattern);
for ($i = 0; $i <= strlen($text) - $len; $i++) {
$substring = substr($text, $i, $len);
$distance = levenshtein($substring, $pattern);
if ($distance <= $maxDistance) {
$matches[] = [
'position' => $i,
'match' => $substring,
'distance' => $distance
];
}
}
return $matches;
}
$text = "ATCGGCTAGC";
$pattern = "ATCG";
$results = approximateMatch($text, $pattern, 1);
print_r($results);
完整的序列匹配类
<?php
class SequenceMatcher {
private $algorithms = ['exact', 'fuzzy', 'kmp', 'smith_waterman'];
public function match($seq1, $seq2, $algorithm = 'exact') {
switch ($algorithm) {
case 'exact':
return $this->exactMatch($seq1, $seq2);
case 'fuzzy':
return $this->fuzzyMatch($seq1, $seq2);
case 'kmp':
return $this->kmpSearch($seq1, $seq2);
case 'smith_waterman':
return $this->smithWaterman($seq1, $seq2);
default:
throw new InvalidArgumentException("Unknown algorithm: $algorithm");
}
}
private function exactMatch($seq1, $seq2) {
return strpos($seq1, $seq2) !== false;
}
private function fuzzyMatch($seq1, $seq2, $tolerance = 1) {
if (strlen($seq1) < strlen($seq2)) {
list($seq1, $seq2) = [$seq2, $seq1];
}
for ($i = 0; $i <= strlen($seq1) - strlen($seq2); $i++) {
$substr = substr($seq1, $i, strlen($seq2));
if (levenshtein($substr, $seq2) <= $tolerance) {
return true;
}
}
return false;
}
// 简化版Smith-Waterman
private function smithWaterman($seq1, $seq2) {
$match = 2;
$mismatch = -1;
$gap = -1;
$m = strlen($seq1);
$n = strlen($seq2);
$matrix = array_fill(0, $m+1, array_fill(0, $n+1, 0));
$maxScore = 0;
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
$score = $seq1[$i-1] === $seq2[$j-1] ? $match : $mismatch;
$matrix[$i][$j] = max(
0,
$matrix[$i-1][$j-1] + $score,
$matrix[$i-1][$j] + $gap,
$matrix[$i][$j-1] + $gap
);
$maxScore = max($maxScore, $matrix[$i][$j]);
}
}
return $maxScore > 0;
}
}
// 使用示例
$matcher = new SequenceMatcher();
$sequences = [
"ATCGATCGATCG",
"ATCGCTAGC",
"ATCGGCTA"
];
$pattern = "ATCG";
foreach ($sequences as $seq) {
echo "序列: $seq\n";
echo " 精确匹配: " . ($matcher->match($seq, $pattern, 'exact') ? "是" : "否") . "\n";
echo " 模糊匹配: " . ($matcher->match($seq, $pattern, 'fuzzy') ? "是" : "否") . "\n";
}
选择建议
- 精确匹配：使用
strpos()或 KMP 算法 - 近似/模糊匹配：使用 Levenshtein 距离或正则表达式
- 局部比对：使用 Smith-Waterman 算法
- 大规模数据：考虑使用扩展如
php-seq或数据库函数 - 生物信息学：考虑集成 BioPHP 或其他生物信息学库
根据你的具体需求选择合适的匹配算法,如果是处理DNA/蛋白质序列，建议使用专门的生物信息学库。
