本文主要是介绍Rosalind 040 Distances in Trees，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个问题涉及到图论中的树结构以及如何使用Newick格式来表示树。下面是关键概念的解释和解决问题的方法：
图论中的树理解
-
树中的唯一路径：在树这种图结构中，任意两个节点之间总是存在一条唯一的路径。这种唯一性是因为树是一个连通的、无循环的图。如果两个节点之间存在多条路径，就会形成一个循环，这在树中是不允许的。
-
在系统发育学中的应用：在系统发育学中，树用来表示物种或群体之间的进化关系。两个分类群（物种或群体）之间的距离通常被定义为树中连接它们的唯一路径上的边的数量。这对于理解进化距离非常重要。
Newick格式
Newick格式是一种表示树结构（特别是在系统发育学中）的简洁文本形式。它特别适用于未标记的树或内部节点未标记的树。
- 有根树：在有根树中，连接到同一内部节点的叶子（外部节点）是邻居。Newick格式通过迭代地将这些节点合并为一个单一的节点来表示，合并节点的标签代表合并的叶子。
- 无根树：对于无根树，可以选择任何一个内部节点作为树的根来表示。
- 格式变化：根据节点是否被标记以及树是有根还是无根，格式可能会有所不同。
问题描述
给定一系列以Newick格式表示的树。每棵树后面跟着一对节点。我们的任务是找出每棵树中这两个节点之间的距离。距离定义为连接它们的唯一路径上的边的数量。
https://rosalind.info/problems/nwck/
解决方法
-
解析Newick格式：首先，你需要解析Newick格式来构建树。这涉及到根据文本表示创建节点和边。
-
查找距离：一旦树被构建，就在每棵树中找出指定节点之间的距离。这可以通过简单的深度优先搜索（DFS）或广度优先搜索（BFS）算法来完成，因为在树中任意两个节点之间都有唯一的路径。
-
返回距离：对每对节点在每棵树中计算并返回距离。
样本数据集解析
-
第一棵树:
(cat)dog;和dog cat- 这个Newick格式表示一个有两个节点（
dog和cat）的树，其中cat是dog的邻居（或子节点）。 - 结构可以视为
dog是根节点，cat是它的直接子节点。 - 查询的节点对是
dog和cat。
- 这个Newick格式表示一个有两个节点（
-
第二棵树:
(dog,cat);和dog cat- 这个Newick格式表示一个有两个叶子节点（
dog和cat）的树，这两个节点都是同一个未命名的内部节点的邻居。 - 结构可以看作是一个根节点（未命名），它有两个子节点
dog和cat。 - 查询的节点对同样是
dog和cat。
- 这个Newick格式表示一个有两个叶子节点（
计算距离
在树中，两个节点之间的距离是连接这两个节点的唯一路径上的边的数量。
-
第一棵树的距离:
- 从
dog到cat的路径只有一条边，因此距离是 1。
- 从
-
第二棵树的距离:
- 从
dog到cat需要经过根节点，因此路径上有两条边（dog到根节点，根节点到cat），所以距离是 2。
- 从
代码：
这段代码是用于解析Newick格式的树，并计算其中两个指定节点之间的距离。这段代码使用了BioPython库中的Phylo模块，这是一个专门用于解析和操作生物信息学中的树结构（如系统发育树）的工具。
关键代码：
ancestor = tree.common_ancestor(x, y): 找到节点x和y的最近公共祖先。out.append(len(ancestor.get_path(x)) + len(ancestor.get_path(y))): 计算从最近公共祖先到节点x和y的路径长度，并将它们的和添加到out列表中。
from io import StringIO
from Bio import Phylo
c = open(r'').read().rstrip().split('\n\n')
out = []
for i in c:t, x, y = i.split()tree = Phylo.read(StringIO(t), 'newick')ancestor = tree.common_ancestor(x, y)out.append(len(ancestor.get_path(x)) + len(ancestor.get_path(y)))
print(out)这篇关于Rosalind 040 Distances in Trees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
