【ROSALIND】【练Python，学生信】53 Trie树与模式匹配

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

模式匹配初探（Introduction to Pattern Matching）

Given: A list of at most 100 DNA strings of length at most 100 bp, none of which is a prefix of another.

所给：一个列表，其中包含最多100条DNA序列，每条不超过100bp，相互不为前缀。

Return: The adjacency list corresponding to the trie T for these patterns, in the following format. If T has n nodes, first label the root with 1 and then label the remaining nodes with the integers 2 through n in any order you like. Each edge of the adjacency list of T will be encoded by a triple containing the integer representing the edge's parent node, followed by the integer representing the edge's child node, and finally the symbol labeling the edge..

需得：与这些DNA序列组成的Trie树T对应的邻接表。格式如下：如果T有n个结点，首先将根结点标记为1，然后把其他结点用从2到n的整数标记，顺序任意；T的邻接表中每行代表一个边，有三个内容，第一个是正整数，是该边父结点的标记，第二个正整数是该边子结点的标记，最后是代表这条边的符号。

测试数据

ATAGA

ATC

GAT

测试输出

1 2 A

2 3 T

3 4 A

4 5 G

5 6 A

3 7 C

1 8 G

8 9 A

9 10 T

生物学背景

       在09 确定DNA子序列出现的位置中，我们学习了模序（motif）的概念及如何定位模序。在实际操作中，我们通常需要从一个很长的序列中搜索一组模序。比如，从一个完整基因组中搜索几个基因。为了更好地解决这个问题，需要引入模式匹配的概念，即从一个字符串中搜索一组子串。为了简单起见，开始时我们只要求精确匹配。

       09 确定DNA子序列出现的位置中采用“滑动窗口”算法来扫描待找的子串，这个方法需要反复扫描序列，耗时长。我们希望有方法单次遍历序列就解决问题，Tire树（字典树）这种数据结构可以帮助我们实现目标。

Python背景

       Trie树是一种前缀树，常用来储存字符串，我们以具体例子来介绍一下Trie树。

       上图示包含'apple'， 'apropos'， 'banana'， 'bandana'和'orange'的Trie树，从根节点到叶子结点形成的每个路径就是一个单词。由图可知，Trie树是有根树，从根结点开始，每个单词第一个独有的字符形成一个边（edge），连接根和一个新的顶点（vertex）。随后再看第二个字符，每个单词独有的字符又形成新的边，连接父结点和一个新的顶点……这个过程不停迭代，就形成了整棵树。沿着Trie中从根到叶的任何路径，每条边的符号将拼出集合中每个唯一的字符串（注意：只有集合中没有字符串是另一个字符串的前缀时这句话才成立）。

       我们可以通过定义一个类来实现Trie树，Python中类用class关键字来标记，可以定义每个实例共有的属性和方法。

思路

       本题中Trie树的实现参考了网络上的相关博文，具体可阅读下面这篇博文：https://blog.csdn.net/annilingmo/article/details/80879910。

       本题核心代码可分为两部分：Trie树类的定义和遍历。

       首先来看Trie树的定义。因为题目中已经明确说了所给的每条序列都相互不为前缀，所以这里其实使问题更简化了，我们只需在__init__中初始化类时定义根节点即可。我在这里给根结点中添加了一个元素‘vertex’，记录根结点的编号，以便后续操作。在insert函数中，每次向Trie树中插入一条序列，这里用全局变量num记录结点数。

       Trie树构建完成后，问题就变成了如何把其中的内容读出来。我这里写了tradic函数实现这个功能。观察Trie树的结构不难发现，这是一个多层嵌套的字典，每个结点的编号都是键名为‘vertex’的字典元素的值；而每个边代表的符号都是一个键，值是这个边下面的路径内容形成的字典。利用这种规律，就可以轻松写出问题所需的邻接表。

       详细解释已写入代码注释，在此不再赘述。

P.S. 本题“solution”区下面有很多更好的写法。

代码