在生物学中，3个核苷酸(A，C，T，G)可以组合成一个密码子。生物信息学软件的一个经典任务就是在基因中找到某个特定的密码子。

DNA的存储方法

核苷酸可以表示为4中状态的简单类型IntEnum

from enum import IntEnum
from typing import Tuple, List

Nucleotide: IntEnum = IntEnum('Nucleotide', ('A', 'T', 'C', 'G'))
Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]
Gene = List[Codon]


gene_str: str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

def string_to_gene(s: str) -> Gene:
    gene: Gene = []
    for i in range(0, len(s), 3):
        if (i+2) >= len(s):
            return gene
        codon: Codon = (Nucleotide[s[i]], Nucleotide[s[i+1]], Nucleotide[s[i+2]])
        gene.append(codon)
    return gene

my_gene: Gene = string_to_gene(gene_str)

Python新增了IntEnum, IntEnum允许枚举的成员和整型作比较

线性搜索

基因需要执行的最基本的操作就是搜索指定的密码子，目标就是简单的查找该密码子是否存在于基因中。

线性搜索，顾名思义，就是按照从头到尾，按照原本的顺序进行搜索每个元素，一直查询到结果或者搜索的结尾。

最坏复杂度：O(n)

def line_contains(gene:Gene, key_codon:Codon)->bool:
    for codon in gene:
        if codon == key_codon:
            return True
    return False

提示

当然(list，tuple，range)均已实现了__contains__()方法，这样就能用in操作符在其中搜索某个指定的数据项

例如，执行print(acg in my_gene)语句即可在my_gene中搜索acg并打印出结果

二分搜索

def binary_contains(gene: Gene, key_codon: Codon) -> bool:
    low: int = 0
    high: int = len(gene) - 1
    while low <= high:
        mid: int = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
    return False

通用示例

from __future__ import annotations
from typing import TypeVar, Iterable, Sequence, Generic, List, Callable, Set, Deque, Dict, Any, Optional
from typing import Protocol
from heapq import heappush, heappop

T = TypeVar('T')


def linear_contains(iterable: Iterable[T], key: T) -> bool:
    for item in iterable:
        if item == key:
            return True
    return False


C = TypeVar("C", bound="Comparable")


class Comparable(Protocol):
    def __eq__(self, other: Any) -> bool:
        pass

    def __lt__(self: C, other: C) -> bool:
        pass

    def __gt__(self: C, other: C) -> bool:
        return (not self < other) and self != other

    def __le__(self: C, other: C) -> bool:
        return self < other or self == other

    def __ge__(self: C, other: C) -> bool:
        return not self < other


def binary_contains(sequence: Sequence[C], key: C) -> bool:
    low: int = 0
    high: int = len(sequence) - 1
    while low <= high:
        mid: int = (low + high) // 2
        if sequence[mid] < key:
            low = mid + 1
        elif sequence[mid] > key:
            high = mid - 1
        else:
            return True
    return False


if __name__ == "__main__":
    print(linear_contains([1, 5, 15, 15, 15, 15, 20], 5))
    print(binary_contains(["a", "d", "e", "f", "z"], "f"))
    print(binary_contains(["john", "mark", "ronald", "sarah"], "sheila"))

提示

以下内容需要使用pip3 install typing_extensions安装typing_extensions模块，

而后续版本的标准库将会包含整个类型(PEP544)

因此Python的后续版本将不再需要导入该模块，并替换该模块导入部分： from typing import Protocol 替换为 from typing_extensions import Protocol