Study on the Super Eulerian Path and the Sequence Reconstruction

Jia Xingui, Xiao Xiang, Jiang Kaizhong

Abstract


De Bruijn graph and Eulerian path in graph are useful mathematics tools for sequence representation and sequence analysis. In this paper, a weighted De Bruijn graph is first proposed. Each vertex and each edge of the graph is assigned a weight respectively. Then, a super Eulerian path in the weighted De Bruijn graph and its reconstruction algorithm from the weighted De Bruijn graph are proposed. The super Eulerian path is a path which can visit a vertex or a edge multiple times. This work is useful for solving the repetitive region problem of the DNA reconstruction.


Keywords


Weighted incomplete De Bruijn graph; Super Eulerian path; Sequence reconstruction; Vertex degree.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.


Copyright (c) 2016

Copyright © 2016 by Global Publishing Corporation

scholar_logo_lg_2011Sis-Logoezbr

ISSN: 2395-4760

For any Technical Support contact us at editor@gpcpublishing.org, editorglobalpublishing@gmail.com.