Genome Sequencing Using Graph Theory Approach

Genome sequencing is the process of determining in which order the nitrogenous bases also known as nucleotides within a DNA molecule are arranged. Every organism’s genome consists of a unique sequence of nucleotides. These nucleotides bases provide the phenotypes and genotypes of a cell. In mathematics, Graph theory is the study of mathematical objects known as graphs which are made of vertices (or nodes) connected by either directed edges or indirect edges. Determining the sequence in which these nucleotides are bonded can help scientists and researchers to compare DNA between organisms, which can help show how the organisms are related. In this research, we study how graph theory plays a vital part in genome sequencing and different types of graphs used during DNA sequencing. We are going to propose several ways graph theory is used to sequence the genome. We are as well, going to explore how the graphs like Hamiltonian graph, Euler graph, and de Bruijn graphs are used to sequence the genome and advantages and disadvantages associated with each graph.

字典乘积图的Euler性

人们在实践中发现,网络拓扑结构的一些性质能够在某种程度上衡量一个网络的性能如何,网络的可靠性便是其中的一个重要性能指标.分析现实世界中已有网络,如计算机网络、电网以及通讯网络等的可靠性具有重要的理论意义和应用价值.图的字典乘积利用已有规模较小的网络来构建规模较大的网络,且所得大网络的特征值完全由小网络的拓扑结构参数来刻画,并具有良好的性能,而图的欧拉回路与欧拉迹亦在此领域有着广泛的应用.乘积因子图的拓扑结构影响着字典乘积图的拓扑结构.本文主要研究字典乘积图的Euler回路问题和Euler迹问题,利用组合理论和极值构造方法,给出了两图的字典乘积图为Euler回路和Euler迹的一些充分必要条件.

一类拟树的Euler子图

介绍了一类拟树所包含的Euler子图的个数,给出了简洁的计算公式,并进行了严格、详尽的证明.有关结果在理论物理的某些研究中具有重要的理论与应用价值.

两类广义Petersen图的Euler亏格

广义Petersen图P(n,m)是这样的一个图:它的顶点集是{u_i,v_i|i=0,1,…,n-1},边集是{u_iu_(i+1),v_iv_(i+m),u_iu_i|i=0,1,…,n-1},这里m,n是正整数、加法是在模n下且m<[n/2].这篇文章证明了P(2m+1,m)(m≥2)的Euler亏格是1,并且P(2m+2,m)(m≥5)的Euler亏格是2.

Euler图C_m⊙C_n的niche数

研究了图 C_m⊙C_n 的 niche 数,证明所有 Euler 图 C_m⊙C_n 的 niche 数n(C_m⊙C_n)都不超过1,且当(m,n)不属于{(4,6),(4,7),(4,8),(4,9),(5,8),(5,9)}时,C_m⊙C_n 都是 niche 图.

图的最大亏格与重图上的有向Euler闭迹

设 Ｇ为图，利用 Ｇ的（有向）２－重图 ＧＧ上的有向 Ｅｕｌｅｒ闭迹，本文给出了Ｇ的最大亏格的主要决定量－Ｂｅｔｔｉ亏数的一个新表达式．这与文献［３］和［６］中所给出的表达式完全不同．

连通图Euler回路充分性的一个简洁证明

连通图Euler回路充分性的证明在一般文献上的表述并不直观,该文拟将给出一个较为直观简洁的证明.

具有割点的标号Euler图的计数(英文)

本文讨论了具有 k( k≥ 2 )个割点 ,并且所有割点均分布在一个 2 -连通 Euler图的标号 Euler图的计数 .在这里给出了含有 n个 2 -连通 Euler图和 k( k≥ 2 )个割点 ,并且所有割点均分布在其中一个 2 -连通 Euler图的标号 Euler图的指数型生成函数 .

关于Euler公式的一个应用

欧拉公式是研究平面图性质的一个重要工具、利用欧拉公式可以得到许多平面图,特别是一些特殊的平面图的点、边、面的关系。本文利用欧拉公式讨论平面图、外平面图的一些性质。

强乘积图的Euler性

强乘积是一种通过若干规模较小的网络构造出规模较大的网络的方法,由此构造出来的大网络包含小网络作为它的子网络,并且保留了小网络一些好的性质,如连通性、可嵌入性等.强乘积图 G1 - G2 的拓扑结构由乘积因子图 G1 和 G2 的拓扑结构所决定.图的 Euler 迹问题是图论中一个重要的问题,在实践中也有着许多应用.本文通过因子图来研究强乘积图的 Euler 环游和 Euler 通路问题,得出并证明了两个图的强乘积存在 Euler 环游和 Euler 通路的充分必要条件.

无向和有向Euler环游变换图的直径

本文得到了无向和有向Ｅｕｌｅｒ环游交换图的直径的上界．（１）设Ｇ是一个无向Ｅｕｌｅｒ多重图．令Ｑ（Ｇ）＝｛ｖ∈Ｖ（Ｇ）｜ｄｖ的Ｅｕｌｅｒ环游（Ｋ－）变换图Ｅｕ（Ｇ）的直径ｄｉａｍ（Ｅｕ（Ｇ））≤λ（Ｃ）－３．（２）设Ｄ是一个有向Ｅｕｌｅｒ多重图，ｄ（ｖ）＝ｉｄ（ｖ）＝ｏｄ（ｖ），令Ｑ（Ｄ）＝｛ｖ∈Ｖ（Ｄ）｜ｄ（ｖ）≥２｝及。则Ｄ的有向Ｅｕｌｅｒ环游（Ｔ－）变换图Ｅｕ．（Ｄ）的直径我们给出例子说明这两个上界都是最佳可能的．

SDN中基于图分割的自适应带内网络遥测探测路径配置

软件定义网络(SDN)是一种将控制与转发平面分离的新型网络架构,可以基于全局信息进行网络资源的调度和优化,而精确的调度需要对全网信息(包括网络中所有交换设备状态及拓扑中所有链路信息)进行准确的测量.带内网络遥测可以在转发数据包的同时实现相关信息的采集,其中配置全网覆盖的探测路径是带内网络遥测需要解决的关键问题之一.但现有SDN网络中全网覆盖的带内网络遥测路径配置方案存在以下问题:(1)需要提前部署大量探测节点导致维护开销增大;(2)探测路径过长导致探测分组长度超过网络中的MTU值;(3)冗余的探测路径导致测量引入的流量负荷在网络整体流量中占比过大;(4)动态变化拓扑下探测路径调整恢复时间长等.为解决上述问题,提出了SDN中基于图分割的自适应带内网络遥测探测路径配置(ACGS)方法,其基本思想是:利用图分割对网络拓扑图进行划分,通过控制拓扑规模来限制探测路径长度;在分割后的子图中求解欧拉回路得到只遍历子图中有向边一次的探测路径,以避免探测节点数量过多、探测路径冗余度高的问题;并利用局部调整与整体调整相结合的方式解决拓扑动态变化时探测路径恢复时间长的问题.实验结果证明ACGS方法能够在SDN网络环境下,实现探测路径长度适中、探测节点数量较少、探测路径冗余程度更低的全网覆盖带内网络遥测探测路径配置,并实现其在拓扑动态变化后更快速的调整.

图的倍图与补倍图(英文)

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题.对简单图G,如果V(D(G))=V(G)∪V(G′),E(D(G))=E(G)∪E(G′)∪{v_iv_j′|v_i∈V(G),v_j′∈V(G′)且v_iv_j∈E(G)}那么,称D(G)是G的倍图,如果V((?)(G))=V(G)∪V(G′),E((?)(C))= E(G)∪E(G′)∪{v_iv_j′|v_i∈V(G),v_j′∈V(G′)and v_iv_j(?)E(G)},称(?)(C)是G的补倍图,这里G′是G的拷贝.本文研究了D(G)和(?)的色数,边色数,欧拉性,哈密顿性和提出了D(G)的边色数是D(G)的最大度等公开问题.

基于欧拉图的授权扩散拓扑构建与授权撤销

在分散式自主授权模式中,接受授权的用户可以将转授给他的权限再次转授给其他人,经过多步转授的权限扩散与不完全的委托撤销可能导致隐性授权冲突.在以往的授权模型中,模型设计的重点在于如何授权,而对于授权撤销考虑甚少.由于转授权路径生成的随意性,增加了遍历路径完成授权回收的难度.针对授权路径的生成和转授权回收进行研究,引入欧拉图对授权路径构建进行约束,在此基础上给出了授权路径构建算法与转授权路径遍历回收方法,通过有目的的授权路径构建,简化转授权路径遍历过程,解决转授权路径遍历不完全导致的授权撤销不完整问题,防止权限扩散并消除隐性授权冲突.

基于平面图的最短路径算法的研究

研究平面图特殊应用条件下最短路径搜索算法的时间复杂度和空间复杂度 .从应用的角度 ,设计一种新的数据存储结构 ,改进最短路径搜索算法 ,并建立一种简捷的估价函数 ,使基于平面图的动态路径规划算法在时间复杂性和空间复杂性上均达到了线性 ,为进一步解决这一领域内的网络综合分析打下了基础 .

需求响应式公交系统路径优化算法

将需求响应式公交系统路径选择问题抽象为在图中寻找覆盖若干条指定边的欧拉圈问题,提出乘客数量不大于公交车容量和乘客数量大于公交车容量两种情况下的公交车运营组织方式,对第一种情况设计了有效的图论算法,对第二种方式则给出转化为动态规划问题的思路。论文引理证明,第一种算法能寻找到覆盖若干条指定边的最小欧拉圈,并通过有关算例进行了说明。

图论及其应用

图论从诞生至今已近300年,但很多问题一直没有很好地解决。随着计算机科学的发展,图论又重新成为了人们研究讨论的热点,这里给出图论在现实生活中的一些应用。

最小最大路划分的一个启发式算法

首先证明了最小最大路划分问题是困难的,然后利用二分算法给出了特殊情形下的最优算法,最后给出了满足三角不等式的图上的一个启发式算法.

空间弹簧阻尼并联振动模型的键图仿真

键图是振动系统建模的有效方法,它易于描述一维的单自由度和多自由度振动。将键图扩展应用到任意多个弹簧阻尼并联的空间多自由度振动系统,基于牛顿-欧拉法建立空间质量块的键图模型,将其和空间任意个并联的弹簧阻尼模型按照因果关系连接起来,再进一步补充添加角速度变换模块和运动学反解等模块就形成了描述空间多自由度振动系统的一般模型。以一个液压Stewart平台为实例进行仿真,仿真结果验证了模型的正确性,该模型对于研究空间复杂振动系统具有参考价值。