LFR长片段读取技术中最小生成树算法
LFR长片段读取技术中最小生成树算法
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
本人最近开始学习一些基因测序方面的知识，然后在读论文时看到了最小生成树的算法，所以我查阅资料，综合他人之所长，然后自己总结。
提示：这里可以添加本文要记录的大概内容：
例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。
提示：以下是本篇文章正文内容，下面案例可供参考
一、最小生成树算法
最小生成树：构造成连通网的最小代价生成树（MinimumCostSpanningTree）
一个连通图 的生成树是一个极小连通子图，它含有图中全部的顶点，但是只有足有构成一棵树的n-1条边。它有如下性质：
一棵有 n个顶点的生成树有且只有 n−1条边；
如果一个图有 n个顶点和小于 n−1条边，则是非连通图；
如果它多于 n−1条边，则一定有环；
但是有 n−1条边的 n个顶点的图不一定是生成树。（它只是必要条件） 一棵生成树的代价就是树上各边的代价之和。
示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。
二、prim算法 普里姆算法
算法内容
假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。
假设 U 是最小生成树中的顶点集合， TE 是最小生成树中的边的集合
算法从 U={u_{0}}（u_{0}∈V ）， TE={} 开始，重复执行下述操作：
在所有 u ∈ U ， v ∈ V − U 的边 ( u , v ) ∈ E (u,v) 中找一条代价最小的边 (u 0,v 0 ) 并入集合TE，同时 v 0并入U，直到 U=V 为止。
此时TE中必有 n−1 条边，则T=（V,{TE}）为N的最小生成树。注意，每次在选择最小边 (u 0,v 0) 时候，需要判断点 v 0 是否已经并入集合 U, 即判断该边的加入是否会产生环路。
简单来说，就是从任意点u0出发，然后不断在所有U中顶点的邻接边中找一个加入不会构成环的顶点并入U直到U=V
我个人的理解：
存在网N，有顶点集V，最小生成树中的顶点集合U，最小生成树的边集合TE
根据PRIM算法
N=（V，{E}）
算法步骤
1）首先仅有一点u_0∈U,该点可以任取，网N中剩下所有点属于V-U集合中。
然后在u_0点出发，在V-U中找一点与u_0代价最小，并连之。该点命名u_1,归属于U。
2）在新的U中，U中所有点都可以找自己与V-U集合中代价最小的点，相比之下，得到最小代价点为u_2,并将两点连在一起，u_2,归属与U。
3）依次执行，直到最终U=V时结束。
总结
以上时我对最小生成树的理解，至于详细内容，如何用代码实现，我推荐看下面的一个博客。
提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
详细内容参考博客
https://blog.****.net/Africa_South/article/details/88608619?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160317416419195240421056%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160317416419195240421056&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_v2~rank_v28-2-88608619.pc_first_rank_v2_rank_v28&utm_term=%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E6%93%8D%E4%BD%9C&spm=1018.2118.3001.4187