PyGTED: Python Application for Computing Graph Traversal Edit Distance - PubMed Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2020 Mar;27(3):436-439.
doi: 10.1089/cmb.2019.0510.

PyGTED: Python Application for Computing Graph Traversal Edit Distance

Ali Ebrahimpour Boroojeny  1 , Akash Shrestha  1 , Ali Sharifi-Zarchi  2 , Suzanne Renick Gallagher  1 , Süleyman Cenk Sahinalp  3 , Hamidreza Chitsaz  1
Affiliations

PyGTED: Python Application for Computing Graph Traversal Edit Distance

Ali Ebrahimpour Boroojeny et al. J Comput Biol. 2020 Mar.

Abstract

Graph Traversal Edit Distance (GTED) is a measure of distance (or dissimilarity) between two graphs introduced. This measure is based on the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs. GTED was motivated by and provides the first mathematical formalism for sequence coassembly and de novo variation detection in bioinformatics. Many problems in applied machine learning deal with graphs (also called networks), including social networks, security, web data mining, protein function prediction, and genome informatics. The kernel paradigm beautifully decouples the learning algorithm from the underlying geometric space, which renders graph kernels important for the aforementioned applications. In this article, we introduce a tool, PyGTED to compute GTED. It implements the algorithm based on the polynomial time algorithm devised for it by the authors. Informally, the GTED is the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs.

Keywords: clustering genera; coassembly; de novo variation detaction; graph comparison; graph kernel; linear programming.

PubMed Disclaimer

Conflict of interest statement

The authors declare they have no conflicting financial interests.

Similar articles

See all similar articles

Cited by

  • Graph Traversal Edit Distance and Extensions.
    Ebrahimpour Boroojeny A, Shrestha A, Sharifi-Zarchi A, Gallagher SR, Sahinalp SC, Chitsaz H. Ebrahimpour Boroojeny A, et al. J Comput Biol. 2020 Mar;27(3):317-329. doi: 10.1089/cmb.2019.0511. Epub 2020 Feb 13. J Comput Biol. 2020. PMID: 32058803 Free PMC article.

References

    1. Boroojeny A.E., Shrestha A., Sharifi-Zarchi A., et al. . 2018. Gted: Graph traversal edit distance, 37–53. In International Conference on Research in Computational Molecular Biology. Springer, Paris, France
    1. Ebrahimpour Boroojeny A. 2019. Theory of Graph Traversal Edit Distance, Extensions, and Applications. Ph.D. Thesis. Available from ProQuest Dissertations & Theses Global database. (Accession Order No. AAT 13812734)
    1. Ebrahimpour Boroojeny A., Shrestha A., Sharifi-Zarchi A., et al. . 2020. Graph traversal edit distance and extensions. J. Comp. Biol. 27 (this issue) - PMC - PubMed
    1. Shariat Razavi S.B., Movahedi Tabrizi N.S., Chitsaz H., et al. . 2014. HyDA-Vista: Towards optimal guided selection of k-mer size for sequence assembly. BMC Genomics 15(Suppl 10), S9. Also GIW/ISCB-Asia proceedings - PMC - PubMed
    1. Smith T.F., and Waterman M.S.. 1981. Identification of common molecular subsequences. J Mol Biol 147, 195–197 - PubMed

LinkOut - more resources