130
个编辑
更改
跳到导航
跳到搜索
第2行：
第2行： − + 第8行：
第8行： − 梯径包括一系列生成操作，用于逐步构建目标对象。一个梯径本质上是一系列构建（或称“进化”）生成的序列，通过这些生成步骤将更小的组件（称为梯元，ladderon）组合成日益复杂的结构。这些阶梯子可以在构建步骤中重复使用，它们的组装关系可以通过一个偏序多重集（partially‑ordered multiset）或一个梯图（laddergraph）来捕捉。从这个表示中，衍生出两个互补的度量指标：+ 第23行：
第23行： − 梯径理论的发展源于一个长期存在的挑战：如何在不依赖统计集合或无限数据集的情况下，测量单个对象（如序列、分子或模式）的句法复杂性（syntactic complexity）。+ 第44行：
第44行： − + − 在这一概念基础上发展起来的组装理论（Assembly Theory，由克罗宁（Cronin）、沃克（Walker）等人开创），将“追溯从基本组件构建对象所需的最小组装操作序列”这一思想形式化，从而提供了一种称为组装指数（assembly index）的度量<ref name=":0">Marshall, S.M., Mathis, C., Carrick, E. ''et al.'' Identifying molecules as biosignatures with assembly theory and mass spectrometry. ''Nat Commun'' 12, 3033 (2021). <nowiki>https://doi.org/10.1038/s41467-021-23258-x</nowiki></ref>。该指数有助于区分可能由生物或技术过程塑造的对象与偶然产生的对象，为探测生物特征（biosignatures）和生命起源开辟了道路。+ − + − 在此基础上，梯径理论通过提供一个层级化的路径模型——一个由可重用构建块组成的“阶梯”（ladder），扩展并形式化了这些先前的思想。通过这个模型，单个对象可以在最优效率的步骤中被构造出来。该方法能够同时量化生成的新颖性（需要多少新的构建步骤）和重用或结构的程度，而无需诉诸基于统计集合的方法。 − − === 组装理论 === − 组装理论提供了一个量化单个分子结构内在复杂性的框架，其核心思想是：考虑从一组预定义的基本构建模块（例如化学键）出发，构建目标分子所需的最少组装步骤序列——每一步骤都涉及将两个分子亚基连接起来。一条组装路径在形式上表示为一个有向多重图：其中顶点对应分子片段，边对应连接操作；多重边允许相同片段存在不同的组合方式。分子的分子组装指数（MA） 定义为构建该分子的最短可能组装路径的长度（即连接操作的数量），并允许路径中生成的中间片段在后续步骤中复用<ref name=":0" /><ref name=":2">Marshall, S.M., Mathis, C., Carrick, E. ''et al.'' Identifying molecules as biosignatures with assembly theory and mass spectrometry. ''Nat Commun'' 12, 3033 (2021). <nowiki>https://doi.org/10.1038/s41467-021-23258-x</nowiki></ref>。 − − − − 第63行：
第55行： − 梯径理论，旨在通过关注结构的层级化、基于组装的本质来解决这些局限性。和组装理论（Assembly Theory）密切相关 ，梯径理论通过最小化“组装指数（assembly index）”——即通过可重用的子结构构造一个对象所需的最少步骤数——来度量复杂性。+ − + 第77行：
第69行： − + − + 第116行：
第108行： − + 第135行：
第127行： − +
→概述
== 概述 ==
== 概述 ==
由刘宇（Yu Liu）、狄增如（Zengru Di）和菲利普·格利（Philip Gerlee）于2022年提出的梯径方法，基于算法信息论，是一种新颖的框架，用于量化某对象（如字符串、空间模式、分子或语言片段）的复杂性和信息<ref>https://www.mdpi.com/1099-4300/24/8/1082</ref>。
由刘宇（Yu Liu）、狄增如（Zengru Di）和菲利普·格利（Philip Gerlee）于2022年提出的梯径方法，基于算法信息论和Evolutionary Tinkering的思想，是一种新颖的框架，用于量化某对象（如字符串、空间模式、分子或语言片段）的复杂性和信息<ref>https://www.mdpi.com/1099-4300/24/8/1082</ref>。
梯径包括一系列生成操作，用于逐步构建目标对象。每一步，可重复使用的较小的子结构单元会被组合或连接起来。经过梯径重构的步骤后，整个序列会形成一个偏序多重集或梯图，用于捕获层次依赖关系。
梯径包括一系列生成操作，用于逐步构建目标对象。每一步，可重复使用的较小的子结构单元会被组合或连接起来。经过梯径重构的步骤后，整个序列会形成一个偏序多重集或梯图，用于捕获层次依赖关系。
传统的复杂性度量（如柯尔莫哥洛夫复杂度或香农熵）要么依赖于无限集合，要么在计算上难以处理。相比之下，梯径提供了一种构造性的、层级化的视角，强调对象如何通过利用重复和重用来合理地构建。
传统的复杂性度量（如柯尔莫哥洛夫复杂度或香农熵）要么依赖于无限集合，要么在计算上难以处理。相比之下，梯径提供了一种构造性的、层级化的视角，强调对象如何通过利用重复和重用来合理地构建。
梯径包括一系列生成操作，用于逐步构建目标对象。一个梯径本质上是一系列构建（或称“进化”）生成的序列，通过这些生成步骤将更小的组件（称为梯元，ladderon）组合成日益复杂的结构。这些阶梯子可以在构建步骤中重复使用，它们的组装关系可以通过一个偏序多重集（partially ordered multiset）或一个梯图（laddergraph）来捕捉。从这个表示中，衍生出两个互补的度量指标：
- 梯径度（<math>\lambda</math>）：表示通过最优重用组件来构造对象所需的最少步骤数。
- 梯径度（<math>\lambda</math>）：表示通过最优重用组件来构造对象所需的最少步骤数。
=== 单个对象的句法复杂性度量 ===
=== 单个对象的句法复杂性度量 ===
梯径理论的发展源于一个长期存在的挑战：如何在不依赖统计集合或无限数据集的情况下，测量单个对象（如序列、分子或模式）的句法复杂性。
柯尔莫哥洛夫复杂度（Kolmogorov complexity）和香农熵（Shannon entropy）等经典方法提供了宝贵的见解，但存在固有的局限性：柯尔莫哥洛夫复杂度因停机问题（halting problem）而通常不可计算；而香农熵则只反映平均不确定性聚焦于跨统计集合的平均值，而忽略了序列内部模式、语法结构，具体为：
柯尔莫哥洛夫复杂度（Kolmogorov complexity）和香农熵（Shannon entropy）等经典方法提供了宝贵的见解，但存在固有的局限性：柯尔莫哥洛夫复杂度因停机问题（halting problem）而通常不可计算；而香农熵则只反映平均不确定性聚焦于跨统计集合的平均值，而忽略了序列内部模式、语法结构，具体为：
香农熵对于单个对象的句法复杂性度量的不足在于，香农熵度量的是从一个已知概率分布中抽样时的平均信息量，而非针对某一具体样本的独特结构。即使两条序列内部模式、语法结构截然不同，只要它们在整体分布下的符号频率相同，香农熵给出的值也完全相同，无法区分个体间的细节差异。
香农熵对于单个对象的句法复杂性度量的不足在于，香农熵度量的是从一个已知概率分布中抽样时的平均信息量，而非针对某一具体样本的独特结构。即使两条序列内部模式、语法结构截然不同，只要它们在整体分布下的符号频率相同，香农熵给出的值也完全相同，无法区分个体间的细节差异。
鉴于这些挑战，一些强调模块化重用和层级化组合的观点提供了引人注目的替代方案。这些观点包括弗朗索瓦·雅各布（François Jacob）提出的“进化即修补”（evolution as tinkering, 1977）概念、高德纳（Donald Knuth）的加法链问题（addition-chain problem）<ref name=":1" />，以及更近期的路径复杂性（pathway complexity）和组装空间理论（assembly space theories）。这些框架关注复杂结构如何从更简单的亚单元构建而成，强调组合效率（combinatorial efficiency）和重复利用（repetition）。
鉴于这些挑战，一些强调模块化重用和层级化组合的观点提供了引人注目的替代方案。这些观点包括弗朗索瓦·雅各布（François Jacob）提出的“进化即修补”（evolution as tinkering, 1977）概念、高德纳（Donald Knuth）的加法链问题（addition-chain problem）<ref name=":1" />、描述Physical Complexity的定量方法<ref>https://journals.aps.org/pre/abstract/10.1103/PhysRevE.82.026117</ref>，及更近期的组装空间理论（Assembly Theory, AT）<ref>https://www.science.org/doi/10.1126/sciadv.abj2465</ref><ref>https://www.science.org/doi/10.1126/sciadv.abj2465</ref>（尽管AT饱受争议且其作者并不承认其跟算法信息论的关系<ref>https://www.nature.com/articles/s41540-024-00403-y</ref>）。这些框架关注复杂结构如何从更简单的亚单元构建而成，强调重复利用。
梯径方法通过提供一个层级化的路径模型——一个由可重用构建块组成的“梯元”（ladderon），扩展并形式化了这些先前的思想。通过这个模型，单个对象可以在最优效率的步骤中被构造出来。该方法能够同时量化生成的新颖性（需要多少新的构建步骤）和重用或结构的程度，而无需诉诸基于统计集合的方法。<span class="lark-record-clipboard" data-lark-record-format="docx/text" data-lark-record-data="{"rootId":"BCUIdvopvozUxkxOYXDcOioYnEh","text":{"initialAttributedTexts":{"text":{"0":"组装理论"},"attribs":{"0":"*0+4"}},"apool":{"numToAttrib":{"0":["author","7359408791762321412"]},"nextNum":1}},"type":"text","referenceRecordMap":{},"extra":{"channel":"saas","isEqualBlockSelection":false,"pasteRandomId":"8391a78e-e4d2-42b4-be74-2ed57aed4cfa","mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"isFromCode":false,"selection":[{"id":36,"type":"text","selection":{"start":4,"end":8},"recordId":"SXLBd6fJCo2LNnxuC7GcAAWmnOf"}],"payloadMap":{},"isCut":false}"></span>
== 梯径方法的框架：算法信息论 ==
<span class="lark-record-clipboard" data-lark-record-format="docx/text" data-lark-record-data="{"rootId":"BCUIdvopvozUxkxOYXDcOioYnEh","text":{"initialAttributedTexts":{"text":{"0":"组装理论"},"attribs":{"0":"*0+4"}},"apool":{"numToAttrib":{"0":["author","7359408791762321412"]},"nextNum":1}},"type":"text","referenceRecordMap":{},"extra":{"channel":"saas","isEqualBlockSelection":false,"pasteRandomId":"8391a78e-e4d2-42b4-be74-2ed57aed4cfa","mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"isFromCode":false,"selection":[{"id":36,"type":"text","selection":{"start":4,"end":8},"recordId":"SXLBd6fJCo2LNnxuC7GcAAWmnOf"}],"payloadMap":{},"isCut":false}"></span>[[文件:A,以分子键为构建模块的二乙基邻苯二甲酸酯分子组装路径图.png|缩略图|588x588像素|以分子键为构建模块的二乙基邻苯二甲酸酯分子组装路径图。该图展示了从不可约构建模块出发，通过8次连接操作（组装指数为8）构建该分子的路径<ref name=":2" />。]]
== 梯径理论的框架：算法信息论 ==
=== 由算法信息论引导的复杂性度量——单个结构化对象的信息 ===
=== 由算法信息论引导的复杂性度量——单个结构化对象的信息 ===
===梯径方法和算法信息论的联系===
===梯径方法和算法信息论的联系===
梯径方法旨在通过关注结构的层级化、基于组装的本质来解决这些局限性。通过可重用的子结构构造一个对象所需的最少步骤数来度量复杂性。
梯径理论和 AIT紧密相关（两者都寻求对象的最短描述），然而在范围和可计算性上稍有不同。它不是进行通用压缩，而是模拟一个领域特定的构造机器，该机器执行一系列组合操作（连接、键合等），并在一个组装池（assembly pool）中跟踪可重用的子单元。这产生了构建过程的层级化多重集表示（梯图，laddergraph），从而得到两个可计算的度量：
梯径理论和 AIT紧密相关（两者都寻求对象的最短描述），然而在范围和可计算性上稍有不同。它不是进行通用压缩，而是模拟一个领域特定的构造机器，该机器执行一系列组合操作（连接、键合等），并在一个池子中跟踪可重用的子单元。这产生了构建过程的层级化多重集表示（梯图，laddergraph），从而得到两个可计算的度量：
-梯径度（<math>\lambda</math>, ladderpath-index）：重构目标序列结构最少的组装步骤数。
-梯径度（<math>\lambda</math>, ladderpath-index）：重构目标序列结构最少的组装步骤数。
* AIT 提供了一种基于最短通用描述的信息度量原则，但通常是不可计算的。
* AIT 提供了一种基于最短通用描述的信息度量原则，但通常是不可计算的。
* 基于组装理论，梯径理论提出了一种可计算的、考虑层级结构的复杂性度量，其基础是构造规则和重用，使其适用于物理和生物系统。
* 梯径方法提出了一种可计算的、考虑层级结构的复杂性度量，其基础是构造规则和重用，使其适用于物理、生物等系统。
* AIT和梯径在深层理论上有联系——都寻求最短描述。但在实用性、侧重点以及对显式组装路径（explicit assembly pathways） 与通用计算（universal computation） 上存在差异。
* AIT和梯径在深层理论上有联系——都寻求最短描述。但在实用性、侧重点以及重构路径的显式描述上存在差异。
== 定义 ==
== 定义 ==
1. 梯径度（[math]\displaystyle{\lambda}[/math], Ladderpath-index）：
1. 梯径度（[math]\displaystyle{\lambda}[/math], Ladderpath-index）：
- 此指数衡量在考虑阶梯元重用的前提下，构造对象所需的最少的组装步骤数，即最短梯径的长度。
- 此指数衡量在考虑阶梯元重用的前提下，构造对象所需的最少的步骤数，即最短梯径的长度。
2. 规模度（[math]\displaystyle{S}[/math],Size-index）:
2. 规模度（[math]\displaystyle{S}[/math],Size-index）:
- 一个组件的最短的平凡梯径的长度。
- 一个组件的最短的平凡梯径的长度。
5. 最后，需要将 H 中各字符串的层次关系（即，根据它们是如何被分割的：谁是父字符串，谁是子字符串）排列清楚，即最终得到该梯径的偏序多重集表示。
5. 最后，需要将 H 中各字符串的层次关系（即，根据它们是如何被分割的：谁是父字符串，谁是子字符串）排列清楚，即最终得到该梯径的偏序多重集表示。
该算法可通过 GitHub 仓库获取：https://github.com/yuernestliu/ladderpath_v0
该算法可通过 GitHub 仓库获取：[https://github.com/yuernestliu/lppack https://github.com/yuernestliu/ladderpath_v0]
== 应用 ==
== 应用 ==