欧拉最早开启图论这方面的研究起源于七座桥连接的两个岛屿和两岸的旅游路径问题。GVE若G为连通图G中经过每条边一次且仅一次的通路称为欧拉通路。如果起点和终点重合即欧拉通路是个回路称为欧拉回路。具有欧拉回路的图称为欧拉图。哈密顿通路是经过每个顶点一次且仅一次的通路。如果是回路则为哈密顿回路存在哈密顿回路的图称为哈密顿图。无向图G具有欧拉通路的条件当且仅当G无奇度顶点回路或有两个奇度顶点为欧拉通路的端点。而哈密顿图的充要条件似乎目前数学界还没有找到下面给几个例子。那么基因组的组装又是如何完成的和哈密顿图和欧拉图又有什么关系呢2001年人类基因组草图首次完成主要使用的是sanger测序法其测序长度较之后来出现的二代测序要长要准确。当时就是把基因组打碎成很多段一段一段的测序然后将所有片段根据相互重叠的区域拼接起来称为完整的基因组序列。举个例子假设有一个环状基因组序列ATGGCGTGCAlen10当然实际基因组要大得多测得的读段reads分别为CGTGCAA, ATGGCGT, CAATGGC, GGCGTGC 和 TGCAATGlen都是7其实测到的分别是5~1, 1~7, 9~5, 3~9, 7~3。reads之间有overlap. 2001年的项目使用的组装方法是将read看作node节点, reads之间有overlap用有向边表示。那么找到哈密顿通路或回路就找到了一条包含这5条reads各出现一次的组装结果序列。于是我们成功的重构了原序列。如下图bHamiltonian cycle方法步骤每个k-mer作为顶点有suffix与perfix长度为k-1 或k-2 等长度的重叠则连一条有向边这样就形成了一个图。任务就是找一条环路访问每个顶点一次。这样就形成了长度最短的candidate genome序列。至于为什么要访问每个顶点一次这是一种理想化的数学建模是一种能复原出最短的包含所有k-mer的序列并不一定是真实的序列在测序错误重复序列基因组倍性与杂合性等情况下组装软件需要突破这种规则实现序列复原。实际中常用比真实reads短的k-mers来作为顶点进行图的构建。一个k-mer除第一个碱基后面的序列和另一个k-mer除最后一个碱基即从开头到倒数第二各碱基之间如果序列一样则这两个k-mer 之间存在一条有向边。比如上图c. 在这样的图中找到一条哈密顿通路回路或环也可以重构初原基因组序列。一般read长度为100bp的话用的k-mer长度通常是55 k-mer,即一个read可以分成46个相互重叠的k-mer。哈密顿通路(环)同时也是包含所有k-mer片段的最短的可能序列。overlap-layout-consensus OLC方法de Bruijn graphs哈密顿图问题要比欧拉图在计算上更加复杂是一个NP问题。实际中只有一些桑格测序的组装如人或微生物基因组组装成功用Hamiltonian方法复原了序列即便如此计算负担也很大。所有大多数二代测序项目换了一种算法将k-mer作为边而不是顶点找到一条通路经历所有的边且只经历一次。就是de Bruijn 图问题。他的大致步骤是如图dform a node for every distinct prefix or suffix of a k-mer, meaning that a given sequence of length k–1 can appear only once as a node of the graph.connect node x to node y with a directed edge if some k-mer (e.g., ATG) has prefix x (e.g.,AT) and suffix y (e.g., TG)实际中有很多问题例如在上面的基础上如果有重复序列ATGC就会形成下图。de nove 的技术现在已经发展出 colored de bruijn graph等算法和技术不仅用在assemble也用在variation calling(包括sv,snp,indel) 两者融合了参见MathPracticeNote/note06.ipynb at main · ruiliuacd/MathPracticeNote最近生物大数据的问题促使 越来越多的文章和工具产品被开发出来The volume of the data, paradoxically, is the main inhibitor of us actually using the dataMetaGraph could help researchers to ask biological questions of repositories such as the Sequence Read Archive (SRA), a public database containing in excess of 100 million billion DNA lettersThey tackled the problem through the use of mathematical ‘graphs’ that links overlapping DNA fragments together, much like sentences that share the same words lining up in a book index说的就是上述图理论在序列组装上的应用。研究者使用MetaGraph https://metagraph.ethz.ch/track drug-resistance genes in bacterial strains that live in subway systems across major urban centres文章open-access: https://www.nature.com/articles/s41586-025-09603-w类似的大规模序列搜索工具还有Chikhi and Babaian 构建的Logan. logan-search.org 帮助了研究者发现了超过2亿中天然存在于细菌真菌和甲虫中的能分解塑料的酶。大数据方面最近还见到一篇Dark proteome发现以及构建病毒数据库Pathogens的报道。