planeGraph2tree

[Correspondence: wangfeiqi@kuicr.kyoto-u.ac.jp]
planeGraph2tree is a software tool for identifying the topological centoroid of an input plane graph and transforming the plane graph to a tree structure. Its algorithm is based on PEELING procedure devised in Akutsu et al. and can be applied to comparson of pseudoknotted RNA secondary structures Wang et al..

Requirement

This tool works on Microsoft Visual Studio and an input plane graph is given as a text file (.txt) described in BPSEQ format.

BPSEQ format simply represents data structure by three columns; i) the first column is the index ordered from 5’ to 3’ for an RNA sequence, ii) the second column contains the label that acronym of nucleotide type which is either of A, U, G, C, X, or Y, where X and Y means the nucleotide would be any type and C or U, respectively, and iii) the third column informs the index of paired partner for the nucleotide, and it is set to be 0 if the nucleotide is unpaired.

Usage(Windows Visual Studio)

• STEP 1 : Open a solution file CanonicalFormComputing.sln in the directory of CanonicalFormComputing on Microsoft Visual Studio.

• STEP 2 : The main file is CanonicalFormComputing.cpp. First, specify an input file name by modifying the following line in the main file.

string fileName = "example";

The BPSEQ format is transformed to DCEL format by creating an instance of DCBLformTransfer class and running formTransfer method.

DCELformTransfer DT; 
DT.formTransfer(fileName);

A tree corresponding the DCEL formatted data is generated by creating an instance of PlaneGraph class and running buildGraph and RUNNING methods. The resulting tree is called a topological centroid tree, which is a tree having its topological centoroid identified by PEELING as the root.

PlaneGraph PG; 
PG.buildGraph(fileName + "_ver.txt", fileName + "_edge.txt", fileName + "_face.txt"); PG.setOuterFace(fileName +"_outerF.txt"); 
PG.RUNNING();

If the topological centroid is either an edge or a face, one of the vertices constituting them is determined as the root. As a result, multiple topological centroid trees are generated from one input plane graph. See [Wang et al.](to be submitted) for more details. The following procedure generates the multiple possibilities.

rootTrans RT; 
RT.running(fileName);

Besides, we newly offer the function that lets every vertex as root to build the tree. If you want to use it, input following codes:

PG.APTEDformTrans_AllVerAsRoot();

Then click RUN BUTTON "Local Windows Debugger" and wait for program finish.

• STEP 3 : Find resulting text files containing tree structure informations described in a bracket-format in the output-directory named tree_result_MutiRoot and tree_result_allVerAsRoot..

Usage(Mac OS Xcode)

• STEP 1 : Open a solution file CanonicalFormComputing_mac.xcodeproj in the directory of CanonicalFormComputing_mac on Xcode.

• STEP 2 : Go to Product -> Scheme -> Edit Scheme... On the tab Options choose yourDirectory/CanonicalFormComputing_mac/CanonicalFormComputing_mac as working directory.

• STEP 3 : The main file is main.cpp. First, specify an input file name by modifying the following line in the main file.

string fileName = "example";

The BPSEQ format is transformed to DCEL format by creating an instance of DCBLformTransfer class and running formTransfer method.

DCELformTransfer DT; 
DT.formTransfer(fileName);

A tree corresponding the DCEL formatted data is generated by creating an instance of PlaneGraph class and running buildGraph and RUNNING methods. The resulting tree is called a topological centroid tree, which is a tree having its topological centoroid identified by PEELING as the root.

PlaneGraph PG; 
PG.buildGraph(fileName + "_ver.txt", fileName + "_edge.txt", fileName + "_face.txt"); PG.setOuterFace(fileName +"_outerF.txt"); 
PG.RUNNING();

If the topological centroid is either an edge or a face, one of the vertices constituting them is determined as the root. As a result, multiple topological centroid trees are generated from one input plane graph. See [Wang et al.](to be submitted) for more details. The following procedure generates the multiple possibilities.

rootTrans RT; 
RT.running(fileName);

Besides, we newly offer the function that lets every vertex as root to build the tree. If you want to use it, input following codes:

PG.APTEDformTrans_AllVerAsRoot();

Then click RUN BUTTON and wait for program finish.

• STEP 4 : Find resulting text files containing tree structure informations described in a bracket-format in the output-directory named tree_result_MutiRoot and tree_result_allVerAsRoot.

Tree Comparison Program

Requirement

This program could be run in Linux or Mac environment based on R. If you have not installed R, you can find it from https://www.r-project.org/ . If you want to run this program in Windows, please download and install Git bash from https://www.git-scm.com/download/win .

Before you use it: This program will download a tree edit distance computation tool called RTED from http://tree-edit-distance.dbresearch.uni-salzburg.at/#download developed by Pawlik et al. .Please make sure your Terminal or Git bash can use wget command.

Usage

• STEP 1 : Right-click comparisonProgram.sh and open it with notepad.

• STEP 2 : Customize input file path and output file name or parameters in the shell file.

• STEP 3 : Input codes below on Linux or Mac Terminal in comparisonProgram.sh directory.

chmod 755 comparisonProgram.sh
./comparisonProgram.sh

Or input codes below on Windows Git bash in comparisonProgram.sh directory.

sh comparisonProgram.sh

Update logs

• 2020.06.29 Fix serveral word mistakes and rename result folder name. Add Mac Xcode version.

• 2020.07.14 Add new method - AllVerAsRoot