PyGTED: Python Application for Computing Graph Traversal Edit Distance.

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.

Graph Traversal Edit Distance and Extensions.

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 give a new graph kernel, which we call graph traversal edit distance (GTED). We introduce the GTED problem and give the first polynomial time algorithm for it. Informally, the GTED is the minimum edit distance between two strings formed by the edge labels of respective Eulerian traversals of the two graphs. Also, GTED is motivated by and provides the first mathematical formalism for sequence co-assembly and de novo variation detection in bioinformatics. We demonstrate that GTED admits a polynomial time algorithm using a linear program in the graph product space that is guaranteed to yield an integer solution. To the best of our knowledge, this is the first approach to this problem. We also give a linear programming relaxation algorithm for a lower bound on GTED. We use GTED as a graph kernel and evaluate it by computing the accuracy of a support vector machine (SVM) classifier on a few data sets in the literature. Our results suggest that our kernel outperforms many of the common graph kernels in the tested data sets. As a second set of experiments, we successfully cluster viral genomes using GTED on their assembly graphs obtained from de novo assembly of next-generation sequencing reads.

Enrichment of ovine gonadotropes via adenovirus gene targeting enhances assessment of transcriptional changes in response to estradiol-17 beta†.

Gonadotropes represent approximately 5-15% of the total endocrine cell population in the mammalian anterior pituitary. Therefore, assessing the effects of experimental manipulation on virtually any parameter of gonadotrope biology is difficult to detect and parse from background noise. In non-rodent species, applying techniques such as high-throughput ribonucleic acid (RNA) sequencing is problematic due to difficulty in isolating and analyzing individual endocrine cell populations. Herein, we exploited cell-specific properties inherent to the proximal promoter of the human glycoprotein hormone alpha subunit gene (CGA) to genetically target the expression of a fluorescent reporter (green fluorescent protein [GFP]) selectively to ovine gonadotropes. Dissociated ovine pituitary cells were cultured and infected with an adenoviral reporter vector (Ad-hαCGA-eGFP). We established efficient gene targeting by successfully enriching dispersed GFP-positive cells with flow cytometry. Confirming enrichment of gonadotropes specifically, we detected elevated levels of luteinizing hormone (LH) but not thyrotropin-stimulating hormone (TSH) in GFP-positive cell populations compared to GFP-negative populations. Subsequently, we used next-generation sequencing to obtain the transcriptional profile of GFP-positive ovine gonadotropes in the presence or absence of estradiol 17-beta (E2), a key modulator of gonadotrope function. Compared to non-sorted cells, enriched GFP-positive cells revealed a distinct transcriptional profile consistent with established patterns of gonadotrope gene expression. Importantly, we also detected nearly 200 E2-responsive genes in enriched gonadotropes, which were not apparent in parallel experiments on non-enriched cell populations. From these data, we conclude that CGA-targeted adenoviral gene transfer is an effective means for selectively labeling and enriching ovine gonadotropes suitable for investigation by numerous experimental approaches.