Evoio - Recent changes [en]

HIP LT Meetings

2012-05-18T16:58:21Z

May 14, 2012:

← Older revision		Revision as of 16:58, 18 May 2012
Line 422:		Line 422:
	= Teleconferences =		= Teleconferences =
	== May 14, 2012 ==		== May 14, 2012 ==
		+	'''present''': Brian, Mike, Rutger, FishMark, SemanticMark, Arlin (presiding), Enrico (recording)
		+	'''absent''': Sergei, Hilmar

	# followup from previous meeting - 12:05		# followup from previous meeting - 12:05

PhylotasticPruningSQL

2012-05-18T16:57:11Z

Get subtree from leaf nodes:

← Older revision		Revision as of 16:57, 18 May 2012
(2 intermediate revisions not shown)
Line 17:		Line 17:
	== Load the species tree ==		== Load the species tree ==

-	This uses a tr_import_species_tree.pl progarm:	+	This uses a [https://github.com/jestill/iplant-treerec/blob/master/scripts/tr_import_species_tree.pl tr_import_species_tree.pl] progarm:

	j-macbook01:scripts jestill$ ./tr_import_species_tree.pl --dbname tr_phylotastic_test -i /Users/jestill/code/phylotastic/trees/rutger_test_tree.tree -u jestill -host localhost --driver mysql -t rutger_test		j-macbook01:scripts jestill$ ./tr_import_species_tree.pl --dbname tr_phylotastic_test -i /Users/jestill/code/phylotastic/trees/rutger_test_tree.tree -u jestill -host localhost --driver mysql -t rutger_test
Line 45:		Line 45:
	== Index the species tree ==		== Index the species tree ==

-	next we add left_index right_index values using the tr_index_species_tree.pl program:	+	next we add left_index right_index values using the [https://github.com/jestill/iplant-treerec/blob/master/scripts/tr_index_species_tree.pl tr_index_species_tree.pl] program:

	j-macbook01:scripts jestill$ ./tr_index_species_tree.pl --verbose --dbname tr_phylotastic_test -u jestill -host localhost --driver mysql		j-macbook01:scripts jestill$ ./tr_index_species_tree.pl --verbose --dbname tr_phylotastic_test -u jestill -host localhost --driver mysql
Line 314:		Line 314:
	10 rows in set (0.07 sec)		10 rows in set (0.07 sec)

-	Also note that this query results in a tree with '''unbranched internal nodes''' that still need to be trimmed. It may be possible to do this by including the transitive closure in the table. or by trimming the tree objects of unbranched internal nodes.

	The above query would of course still need to be translated to a common tree format. In perl this could use [http://www.bioperl.org/wiki/HOWTO:Trees BioPerl TreeIO] or Rutger's [http://search.cpan.org/dist/Bio-Phylo/ Bio::Phylo]		The above query would of course still need to be translated to a common tree format. In perl this could use [http://www.bioperl.org/wiki/HOWTO:Trees BioPerl TreeIO] or Rutger's [http://search.cpan.org/dist/Bio-Phylo/ Bio::Phylo]
		+
		+	Also note that this query results in a tree with '''unbranched internal nodes''' that still need to be trimmed. It may be possible to do this by including the transitive closure table in the query, or by trimming the tree objects of unbranched internal nodes.

Phylotastic

2012-05-18T16:54:19Z

a bit more about the issue of integration and mashups:

← Older revision		Revision as of 16:54, 18 May 2012
(One intermediate revision not shown)
Line 110:		Line 110:
	=== a bit more about the issue of integration and mashups ===		=== a bit more about the issue of integration and mashups ===

-	The main work of this project is to develop the "engine", the stuff that is "under the hood". ~~However, the reason we are doing~~ this is ~~so that it is easier for~~ users all over the world, ~~in all different areas of science,~~ to ~~put their data in a phylogenetic context~~.	+	The main work of this project is to develop the "engine", the stuff that is "under the hood". But if this is going to benefit users all over the world, we need to show what the engine can do. For this reason, a '''substantial''' fraction of the energy will be devoted to creating integration tools that combine the engine of phylotastic, with species information that is easily gathered via existing services, such as:
-		+
-	~~To illustrate the significance of~~ this, ~~we would like to devote~~ a '''substantial''' fraction of the energy ~~at the hackathon~~ to creating integration tools that combine the engine of phylotastic, with species information that is easily gathered via existing services~~. Here are some of the kinds of useful information that we can collect for a species using online services~~:	+
	* images of an individual of the species, collected from EoL or wikipedia; or silhouettes from [http://phylopic.org/ phylopic]		* images of an individual of the species, collected from EoL or wikipedia; or silhouettes from [http://phylopic.org/ phylopic]
	* geographic distribution of the species, from GBIF		* geographic distribution of the species, from GBIF
Line 121:		Line 119:
	* the average<link rel="shortcut icon" href="/favicon.ico" />		* the average<link rel="shortcut icon" href="/favicon.ico" />
	<link rel="search" type="application/opensearchdescription+xml" href="/wg/evoioaps, is just a web form with a place to submit and validate a species list, and a set of check-boxes for which types of information to collect for those species. The user enters the species list, clicks on the desire information, and then clicks "Go", and the software goes and gets the information and the phylogeny, and presents it to the user for visualization (e.g., in Mesquite or some other viewer that can be adapted). For an example species mashup, see Rod Page's [http://ispecies.org ispecies], which creates an on-the-fly web page for a species based on info from NCBI, google scholar, etc		<link rel="search" type="application/opensearchdescription+xml" href="/wg/evoioaps, is just a web form with a place to submit and validate a species list, and a set of check-boxes for which types of information to collect for those species. The user enters the species list, clicks on the desire information, and then clicks "Go", and the software goes and gets the information and the phylogeny, and presents it to the user for visualization (e.g., in Mesquite or some other viewer that can be adapted). For an example species mashup, see Rod Page's [http://ispecies.org ispecies], which creates an on-the-fly web page for a species based on info from NCBI, google scholar, etc
		+
		+	=== thinking about phylotastic in an MVC design pattern ===
		+
		+	'''background''' This is an application of Model-View-Controller or MVC design pattern (http://en.wikipedia.org/wiki/Model–view–controller, or see the discussion here: http://msdn.microsoft.com/en-us/library/ff649643.aspx). In the design sketched below, the model (the M in MVC) is precisely the USER's tree. This may sound odd at first, if you've been thinking of "phylotastic" as a centralized resource with back-end megatrees at its heart. The design below gives us considerable freedom (to imagine different kinds of phylotastic implementations) by abstracting the operations away from the model. It frees us from thinking of a conventional workflow, because many operations can be done asynchronously (e.g., we can decorate OTUs with images before or after getting the topology). Because of this potential for multiple asynchronous operations, it may be helpful to add an "Observer" element to the MVC design.
		+
		+	'''model''' The "model" is the user's tree along with its metadata. Of course, the user typically doesn't begin with a tree, but with a kind of pre-tree. In mathematics its ok for a "graph" to be a set of unlinked nodes. We'll borrow that way of thinking and imagine that the initial state of the tree is (typically) a list of OTUs that will become the terminal nodes. The final state of the tree typically is a fully connected tree with a topology and branch lengths. The final tree may be missing some nodes that could not be found. Also, there may be annotations of individual nodes, and annotations (metadata) for the tree-as-a-whole (e.g., this tree was assembled on a particular date by a particular service).
		+
		+	'''operations''' If that is the model, then here is how we would conceptualize the KINDS of operations that update the model:
		+	* a "TNRS" updates the model by replacing input OTU names, or annotating input names, with qualified OTU names.
		+	* a "topology service" updates the model by linking some or all of the OTUs into a connected graph
		+	* a "scaling service" updates the model by estimating the lengths of branches connecting nodes
		+	* a decorating or annotating service updates the model by adding annotations to nodes or branches, such as
		+	** collecting images of OTUs
		+	** gathering fossil-based dates for internal nodes
		+	** assessing quality or reliability of a node
		+	** and so on
		+
		+	In addition
		+	* every service updates the model by adding provenance information (e.g., describing how it has modified the model)
		+
		+	'''controllers and views''' The typical view of the model is going to be a phylogeny or an OTU-based table. A controller invokes services to modify the model (the user's tree) in response to user commands. Frequently we have discussed phylotastic in terms of automated controllers, such as workflow engines that manage the inputs and outputs of a series of operations. But we also could think of an interactive controller.

	===Background===		===Background===

PhylotasticPruningSQL

2012-05-18T16:29:30Z

Get subtree from leaf nodes:

← Older revision		Revision as of 16:29, 18 May 2012
(8 intermediate revisions not shown)
Line 1:		Line 1:
	= About =		= About =

-	Some notes on pruning a tree in SQL.	+	Some notes on pruning a tree in SQL. It is possible to select subtrees in SQL without recursion using nested set indexing of the species tree.

	= Database Schema =		= Database Schema =

-	Multiple database schema options exist. For this example I will use ~~extensions~~ to the Ensemble Compara database that support species tree.	+	Multiple database schema options exist. For this example I will use tables I've added to the Ensemble Compara database that support species tree. (more details to come)

	= Tree Example =		= Tree Example =
Line 139:		Line 139:

	= Queries for the tree =		= Queries for the tree =
		+
		+	Some of the following queries could include tree name in the query and could be sped up with joins instead of selects, but I am showing these as follows for clarity. So keeping this in mind, the following queries are actually slower than optimized queries would be.

	== Get all Leaf Nodes ==		== Get all Leaf Nodes ==
Line 201:		Line 203:
	+----------------------+-----------------+-----------+-------+------------+-------------+		+----------------------+-----------------+-----------+-------+------------+-------------+
	8 rows in set (0.04 sec)		8 rows in set (0.04 sec)
		+
		+	== Getting LCA ==
		+
		+	It is possible to get the LCA of a set of nodes
		+
		+	-------------------------------------------------------------+
		+	-- GETING LAST COMMON ANCESTOR (LCA) OF A SET OF
		+	-- NODES IN THE SPECIES TREE
		+	-------------------------------------------------------------+
		+	SELECT *
		+	FROM species_tree_node
		+	WHERE left_index < (
		+	SELECT MIN(left_index)
		+	FROM species_tree_node
		+	WHERE label IN ('A', 'C', 'F', 'G')
		+	AND species_tree_id = 3
		+	)
		+	AND right_index > (
		+	SELECT MAX(right_index)
		+	FROM species_tree_node
		+	WHERE label IN ('A', 'C', 'F', 'G')
		+	AND species_tree_id = 3
		+	)
		+	AND species_tree_id = 3
		+	ORDER BY left_index DESC
		+	LIMIT 1;
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	\| species_tree_node_id \| species_tree_id \| parent_id \| label \| left_index \| right_index \|
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	\| 2781 \| 3 \| 0 \| 6 \| 1 \| 26 \|
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	1 row in set (0.03 sec)
		+
		+	This query is NOT limited to leaf node sets:
		+
		+	mysql> SELECT *
		+	-> FROM species_tree_node
		+	-> WHERE left_index < (
		+	-> SELECT MIN(left_index)
		+	-> FROM species_tree_node
		+	-> WHERE label IN ('1', 'E')
		+	-> AND species_tree_id = 3
		+	-> )
		+	-> AND right_index > (
		+	-> SELECT MAX(right_index)
		+	-> FROM species_tree_node
		+	-> WHERE label IN ('1', 'E')
		+	-> AND species_tree_id = 3
		+	-> )
		+	-> AND species_tree_id = 3
		+	-> ORDER BY left_index DESC
		+	-> LIMIT 1;
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	\| species_tree_node_id \| species_tree_id \| parent_id \| label \| left_index \| right_index \|
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	\| 2782 \| 3 \| 2781 \| 4 \| 2 \| 19 \|
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	1 row in set (0.00 sec)
		+
		+	== Get subtree from leaf nodes ==
		+
		+	As a function this type of query would require the tree name and an array of label names to select. As an example, in a database where the tree_id of interest is 3, and the set of leaf nodes of interest if A,C,F,G.
		+
		+	mysql> SELECT * FROM species_tree_node WHERE left_index IN (
		+	-> SELECT np.left_index
		+	-> FROM species_tree_node nc
		+	-> JOIN species_tree_node np
		+	-> ON nc.left_index >= np.left_index
		+	-> AND nc.left_index <= np.right_index
		+	-> WHERE nc.label IN ( 'A', 'C', 'F', 'G' )
		+	-> AND np.species_tree_id = 3
		+	-> )
		+	-> AND species_tree_id = 3
		+	-> AND left_index >= (
		+	-> SELECT left_index FROM
		+	-> species_tree_node WHERE left_index =
		+	-> (
		+	-> SELECT MAX(left_index)
		+	-> FROM species_tree_node
		+	-> WHERE left_index < (
		+	-> SELECT MIN(left_index)
		+	-> FROM species_tree_node
		+	-> WHERE label IN ( 'A', 'C', 'F', 'G')
		+	-> AND species_tree_id = 3
		+	-> )
		+	-> AND right_index > (
		+	-> SELECT MAX(right_index)
		+	-> FROM species_tree_node
		+	-> WHERE label IN ( 'A', 'C', 'F', 'G')
		+	-> AND species_tree_id = 3
		+	-> )
		+	-> AND species_tree_id = 3
		+	-> )
		+	-> AND species_tree_id = 3
		+	-> );
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	\| species_tree_node_id \| species_tree_id \| parent_id \| label \| left_index \| right_index \|
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	\| 2781 \| 3 \| 0 \| 6 \| 1 \| 26 \|
		+	\| 2782 \| 3 \| 2781 \| 4 \| 2 \| 19 \|
		+	\| 2783 \| 3 \| 2782 \| 3 \| 3 \| 16 \|
		+	\| 2784 \| 3 \| 2783 \| 1 \| 4 \| 9 \|
		+	\| 2785 \| 3 \| 2784 \| A \| 5 \| 6 \|
		+	\| 2787 \| 3 \| 2783 \| 2 \| 10 \| 15 \|
		+	\| 2788 \| 3 \| 2787 \| C \| 11 \| 12 \|
		+	\| 2791 \| 3 \| 2781 \| 5 \| 20 \| 25 \|
		+	\| 2792 \| 3 \| 2791 \| F \| 21 \| 22 \|
		+	\| 2793 \| 3 \| 2791 \| G \| 23 \| 24 \|
		+	+----------------------+-----------------+-----------+-------+------------+-------------+
		+	10 rows in set (0.07 sec)
		+
		+	Also note that this query results in a tree with '''unbranched internal nodes''' that still need to be trimmed. It may be possible to do this by including the transitive closure in the table. or by trimming the tree objects of unbranched internal nodes.
		+
		+	The above query would of course still need to be translated to a common tree format. In perl this could use [http://www.bioperl.org/wiki/HOWTO:Trees BioPerl TreeIO] or Rutger's [http://search.cpan.org/dist/Bio-Phylo/ Bio::Phylo]

PhylotasticSandbox

2012-05-18T15:55:33Z

about:

← Older revision		Revision as of 15:55, 18 May 2012
Line 4:		Line 4:

	* Rutger's [https://github.com/HIP-WG/tolomatic/blob/master/README.pod proof-of-concept] uses map-reduce		* Rutger's [https://github.com/HIP-WG/tolomatic/blob/master/README.pod proof-of-concept] uses map-reduce
		+	* Jamie's [http://www.evoio.org/wiki/PhylotasticPruningSQL notes on using SQL for searches on trees] that have been indexed using [http://www.sitepoint.com/hierarchical-data-database-2/ tree traversal].

PhylotasticPruningSQL

2012-05-18T15:46:45Z

Get all Leaf Nodes:

New page

= About =

Some notes on pruning a tree in SQL.

= Database Schema =

Multiple database schema options exist. For this example I will use extensions to the Ensemble Compara database that support species tree.

= Tree Example =

Using the same simple tree that Rutger used.

= Populating the database =

I wrote some tools to populate this database in perl.

== Load the species tree ==

This uses a tr_import_species_tree.pl progarm:

j-macbook01:scripts jestill$ ./tr_import_species_tree.pl --dbname tr_phylotastic_test -i /Users/jestill/code/phylotastic/trees/rutger_test_tree.tree -u jestill -host localhost --driver mysql -t rutger_test

that adds rows to the species_tree_node table:

mysql> select * from species_tree_node;
+----------------------+-----------------+-----------+-------+------------+-------------+
| species_tree_node_id | species_tree_id | parent_id | label | left_index | right_index |
+----------------------+-----------------+-----------+-------+------------+-------------+
| 2781 | 3 | 0 | 6 | 0 | 0 |
| 2782 | 3 | 2781 | 4 | 0 | 0 |
| 2783 | 3 | 2782 | 3 | 0 | 0 |
| 2784 | 3 | 2783 | 1 | 0 | 0 |
| 2785 | 3 | 2784 | A | 0 | 0 |
| 2786 | 3 | 2784 | B | 0 | 0 |
| 2787 | 3 | 2783 | 2 | 0 | 0 |
| 2788 | 3 | 2787 | C | 0 | 0 |
| 2789 | 3 | 2787 | D | 0 | 0 |
| 2790 | 3 | 2782 | E | 0 | 0 |
| 2791 | 3 | 2781 | 5 | 0 | 0 |
| 2792 | 3 | 2791 | F | 0 | 0 |
| 2793 | 3 | 2791 | G | 0 | 0 |
+----------------------+-----------------+-----------+-------+------------+-------------+
13 rows in set (0.00 sec)

== Index the species tree ==

next we add left_index right_index values using the tr_index_species_tree.pl program:

j-macbook01:scripts jestill$ ./tr_index_species_tree.pl --verbose --dbname tr_phylotastic_test -u jestill -host localhost --driver mysql

that walks the tree and adds left and right index values to the table species_tree_node:

mysql> select * from species_tree_node;
+----------------------+-----------------+-----------+-------+------------+-------------+
| species_tree_node_id | species_tree_id | parent_id | label | left_index | right_index |
+----------------------+-----------------+-----------+-------+------------+-------------+
| 2781 | 3 | 0 | 6 | 1 | 26 |
| 2782 | 3 | 2781 | 4 | 2 | 19 |
| 2783 | 3 | 2782 | 3 | 3 | 16 |
| 2784 | 3 | 2783 | 1 | 4 | 9 |
| 2785 | 3 | 2784 | A | 5 | 6 |
| 2786 | 3 | 2784 | B | 7 | 8 |
| 2787 | 3 | 2783 | 2 | 10 | 15 |
| 2788 | 3 | 2787 | C | 11 | 12 |
| 2789 | 3 | 2787 | D | 13 | 14 |
| 2790 | 3 | 2782 | E | 17 | 18 |
| 2791 | 3 | 2781 | 5 | 20 | 25 |
| 2792 | 3 | 2791 | F | 21 | 22 |
| 2793 | 3 | 2791 | G | 23 | 24 |
+----------------------+-----------------+-----------+-------+------------+-------------+
13 rows in set (0.00 sec)

as well as determines node paths:

mysql> select * from species_tree_node_path (path label uses IDs fro bioperl treeIO representation of the tree):
+---------------------------+----------------+---------------+-------------+----------+
| species_tree_node_path_id | parent_node_id | child_node_id | path | distance |
+---------------------------+----------------+---------------+-------------+----------+
| 80246 | 2781 | 2781 | | 0 |
| 80247 | 2782 | 2782 | | 0 |
| 80248 | 2783 | 2783 | | 0 |
| 80249 | 2784 | 2784 | | 0 |
| 80250 | 2785 | 2785 | | 0 |
| 80251 | 2786 | 2786 | | 0 |
| 80252 | 2787 | 2787 | | 0 |
| 80253 | 2788 | 2788 | | 0 |
| 80254 | 2789 | 2789 | | 0 |
| 80255 | 2790 | 2790 | | 0 |
| 80256 | 2791 | 2791 | | 0 |
| 80257 | 2792 | 2792 | | 0 |
| 80258 | 2793 | 2793 | | 0 |
| 80259 | 0 | 2781 | 1 | 1 |
| 80260 | 2781 | 2782 | 2 | 1 |
| 80261 | 2782 | 2783 | 3 | 1 |
| 80262 | 2783 | 2784 | 4 | 1 |
| 80263 | 2784 | 2785 | 5 | 1 |
| 80264 | 2784 | 2786 | 7 | 1 |
| 80265 | 2783 | 2787 | 10 | 1 |
| 80266 | 2787 | 2788 | 11 | 1 |
| 80267 | 2787 | 2789 | 13 | 1 |
| 80268 | 2782 | 2790 | 17 | 1 |
| 80269 | 2781 | 2791 | 20 | 1 |
| 80270 | 2791 | 2792 | 21 | 1 |
| 80271 | 2791 | 2793 | 23 | 1 |
| 80272 | 0 | 2782 | 1.2 | 2 |
| 80273 | 0 | 2791 | 1.20 | 2 |
| 80274 | 2781 | 2783 | 2.3 | 2 |
| 80275 | 2781 | 2790 | 2.17 | 2 |
| 80276 | 2782 | 2784 | 3.4 | 2 |
| 80277 | 2782 | 2787 | 3.10 | 2 |
| 80278 | 2783 | 2785 | 4.5 | 2 |
| 80279 | 2783 | 2786 | 4.7 | 2 |
| 80280 | 2783 | 2788 | 10.11 | 2 |
| 80281 | 2783 | 2789 | 10.13 | 2 |
| 80282 | 2781 | 2792 | 20.21 | 2 |
| 80283 | 2781 | 2793 | 20.23 | 2 |
| 80284 | 0 | 2783 | 1.2.3 | 3 |
| 80285 | 0 | 2790 | 1.2.17 | 3 |
| 80286 | 0 | 2792 | 1.20.21 | 3 |
| 80287 | 0 | 2793 | 1.20.23 | 3 |
| 80288 | 2781 | 2784 | 2.3.4 | 3 |
| 80289 | 2781 | 2787 | 2.3.10 | 3 |
| 80290 | 2782 | 2785 | 3.4.5 | 3 |
| 80291 | 2782 | 2786 | 3.4.7 | 3 |
| 80292 | 2782 | 2788 | 3.10.11 | 3 |
| 80293 | 2782 | 2789 | 3.10.13 | 3 |
| 80294 | 0 | 2784 | 1.2.3.4 | 4 |
| 80295 | 0 | 2787 | 1.2.3.10 | 4 |
| 80296 | 2781 | 2785 | 2.3.4.5 | 4 |
| 80297 | 2781 | 2786 | 2.3.4.7 | 4 |
| 80298 | 2781 | 2788 | 2.3.10.11 | 4 |
| 80299 | 2781 | 2789 | 2.3.10.13 | 4 |
| 80300 | 0 | 2785 | 1.2.3.4.5 | 5 |
| 80301 | 0 | 2786 | 1.2.3.4.7 | 5 |
| 80302 | 0 | 2788 | 1.2.3.10.11 | 5 |
| 80303 | 0 | 2789 | 1.2.3.10.13 | 5 |
+---------------------------+----------------+---------------+-------------+----------+
58 rows in set (0.00 sec)

= Queries for the tree =

== Get all Leaf Nodes ==

It is simple to get all leaf nodes by using the fact that left and right index values on leaf nodes are separated by 1. The following example assumes a single tree in the database, otherwise for a database with multiple trees you need to add a join that allows you to include the tree_id or tree_name of interest in the query:

mysql> SELECT * FROM species_tree_node
-> WHERE left_index = right_index - 1;
+----------------------+-----------------+-----------+-------+------------+-------------+
| species_tree_node_id | species_tree_id | parent_id | label | left_index | right_index |
+----------------------+-----------------+-----------+-------+------------+-------------+
| 2785 | 3 | 2784 | A | 5 | 6 |
| 2786 | 3 | 2784 | B | 7 | 8 |
| 2788 | 3 | 2787 | C | 11 | 12 |
| 2789 | 3 | 2787 | D | 13 | 14 |
| 2790 | 3 | 2782 | E | 17 | 18 |
| 2792 | 3 | 2791 | F | 21 | 22 |
| 2793 | 3 | 2791 | G | 23 | 24 |
+----------------------+-----------------+-----------+-------+------------+-------------+
7 rows in set (0.04 sec)

and getting the list of labels for the leaf nodes in the tree is

mysql> SELECT label FROM species_tree_node WHERE left_index = right_index - 1;
+-------+
| label |
+-------+
| A |
| B |
| C |
| D |
| E |
| F |
| G |
+-------+
7 rows in set (0.00 sec)

== Get subtree for a given internal node ==

This could use the label for the node in the input tree. For example label = Asteraceae or nc.label=4 in the following example:

mysql> SELECT * FROM species_tree_node
WHERE left_index IN (
SELECT np.left_index
FROM species_tree_node nc
JOIN species_tree_node np
ON nc.left_index < np.left_index
AND nc.right_index > np.right_index
WHERE nc.label = 4 );
+----------------------+-----------------+-----------+-------+------------+-------------+
| species_tree_node_id | species_tree_id | parent_id | label | left_index | right_index |
+----------------------+-----------------+-----------+-------+------------+-------------+
| 2783 | 3 | 2782 | 3 | 3 | 16 |
| 2784 | 3 | 2783 | 1 | 4 | 9 |
| 2785 | 3 | 2784 | A | 5 | 6 |
| 2786 | 3 | 2784 | B | 7 | 8 |
| 2787 | 3 | 2783 | 2 | 10 | 15 |
| 2788 | 3 | 2787 | C | 11 | 12 |
| 2789 | 3 | 2787 | D | 13 | 14 |
| 2790 | 3 | 2782 | E | 17 | 18 |
+----------------------+-----------------+-----------+-------+------------+-------------+
8 rows in set (0.04 sec)

PhylotasticUseCases

2012-05-17T18:11:16Z

Big Trees:

← Older revision		Revision as of 18:11, 17 May 2012
(One intermediate revision not shown)
Line 23:		Line 23:

	* 55,473 taxon '''angiosperm''' phylogeny from Smith et al. 2011, Newick format, species-level ([[File:Smith_2011_angiosperms.txt]])		* 55,473 taxon '''angiosperm''' phylogeny from Smith et al. 2011, Newick format, species-level ([[File:Smith_2011_angiosperms.txt]])
		+	**Nodes with IDs: ''55,473''
		+	**max ID Length: ''63''
		+	**max ID length text: ''Aesculus_glabra_var__arguta_x_Aesculus_sylvatica_var__pubescens''

	* This is the '''angiosperm''' phylogeny group (APG) tree that underlies Phylomatic, NEXUS format, family level ([[File:phylomatictree.nex]])		* This is the '''angiosperm''' phylogeny group (APG) tree that underlies Phylomatic, NEXUS format, family level ([[File:phylomatictree.nex]])
		+	**Nodes with IDs: ''1,827''
		+	**max ID Length: ''34''
		+	**max ID length text: ''harrimanelloideae_to_vaccinioideae''

	* Megaphylogeny of 800+ living and fossil families of '''fishes''', Westneat and Lundberg unpublished, NEXUS format including Mesquite extensions, family level with other higher-taxa labelled ([[File:Westneat_Lundberg_BigFishTree.nex]])		* Megaphylogeny of 800+ living and fossil families of '''fishes''', Westneat and Lundberg unpublished, NEXUS format including Mesquite extensions, family level with other higher-taxa labelled ([[File:Westneat_Lundberg_BigFishTree.nex]])

HIP LT Meetings

2012-05-17T14:30:54Z

May 14, 2012:

← Older revision		Revision as of 14:30, 17 May 2012
Line 424:		Line 424:

	# followup from previous meeting - 12:05		# followup from previous meeting - 12:05
-	#* github	+	#* github: [Rutger] organization has been set up and it seems that the majority of the participants signed up
-	#* dev server	+	#* dev server: [Enrico] Naim indicated
-	#* google+	+	#** Willingness to provide a server with VMs for the development - but the tech support is guaranteed only during "office hours" for the duration of the hackaton; LT discussed and decided that perhaps we could focus on NESCent for the development activities
-	#* web services discussion & possible spec	+	#** Willingness to provide a server for distribution/dissemination; at this time the commitment is until the end of the current funding cycle (2013), but he is confident that new funding will arrive and that will allow the commitment to be extended.
		+	#* google+: Everyone from LT signed up in the shared circle
		+	#* web services discussion & possible spec:
		+	#** LT indicated that it would be ok to wait until the use cases become more concrete
		+	#** Rutger will develop a mock-up of a typical URL and circulate it on the mailing list
	#* use-cases discussion		#* use-cases discussion
		+	#** Lots of exciting ideas and discussion
		+	#** Still not enough in terms of concrete inputs and outputs [Brian follow up on this?]
	# funding & organizing the next hackathon - 12:10		# funding & organizing the next hackathon - 12:10
		+	#* Arlin set up wiki page for discussion and ideas
	# playing nice with each other - 12:25		# playing nice with each other - 12:25
		+	#* discussion postponed
	# hackathon schedule and logistics - 12:35		# hackathon schedule and logistics - 12:35
-	#* ~~overall schedule for~~ presentations, ~~pitches, sub-group~~ formation, and ~~work days~~	+	#* LT approved the idea of including Naim's presentation at NESCent on discovery environment from iPlant
-	#* ~~topics & speakers~~ for ~~presentations on day~~ 1	+	#** Talk during lunch on Tuesday
-	#* the ~~meeting of LT members~~	+	#** HIP will cover the catering of lunch
-	#* ~~possible talk on iPlant's discovery environment~~	+	#* Schedule
-	# ~~adjourn~~ 1:~~00 pm~~	+	## Day 1 Part 1: Presentations focused on use cases/what the users want
		+	##* 3 presentations, perhaps 2 hours
		+	##* Karen solicit on the mailing list ideas and volunteers
		+	##* Enable formation of teams working on each presentation - trying to engage participants (especially those that are less "hackers")
		+	## Day 1 Part 2: Presentation on high level architecture and design
		+	##* Arlin fleshes out the presentation
		+	##* Rutger provides a demo
		+	##* Set overall strategy and create context for group formations
		+	## LUNCH
		+	## Day 1 Part 3: Technical boot camp
		+	##* topics to be decided as feedback from the participants
		+	##* Karen set up googledoc form to collect ideas
		+	##* Some possibilities
		+	##** Rutger: NeXML
		+	##** Enrico: CDAO/PhyloWS
		+	##** Ben: creating web services [Semantic Mark contact him]
		+	##** Helen: semantic annotations [Semantic Mark contact her]
		+	##** Naim: taxonomic name resolution [Enrico contact him]
		+	## BREAK
		+	## Day 1 Part 4: Group formations
		+	##* variation of open model; leaders pitches for the groups
		+	## Day 1 Part 5: social event in a local pub
		+	# Day 2 will start with group presentations to ensure that the vision is formed and focused
		+	# LT face-to-face meeting to be decided on the mailing list

	==April 16, 2012 ==		==April 16, 2012 ==

PhylotasticDatastore

2012-05-16T21:46:30Z

Additional Information:

← Older revision		Revision as of 21:46, 16 May 2012
(5 intermediate revisions not shown)
Line 1:		Line 1:
	= About =		= About =

-	Information on various options that could be used as datastores to host the trees underlying the	+	Information on various options that could be used as datastores to host the trees underlying the phylotastic service that prunes trees.

	= Requirements =		= Requirements =
Line 61:		Line 61:
	! PostgreSQL		! PostgreSQL
	\|-		\|-
-	\| Max allowed packet	+	\| Max allowed packet (a limit on the list of species for trimming the tree)
	\| By default this is 1 MB but can be increased		\| By default this is 1 MB but can be increased
	\|		\|
	\|-		\|-
	\| Forced Referential integreity		\| Forced Referential integreity
-	\| Yes ([http://www.sitepoint.com/mysql-innodb-table-pros-cons/ with InnoDB tables])	+	\| Yes ([http://www.sitepoint.com/mysql-innodb-table-pros-cons/ with InnoDB tables] but these generally are slower than [http://www.kavoir.com/2009/09/mysql-engines-innodb-vs-myisam-a-comparison-of-pros-and-cons.html MyISAM tables])
	\| Yes		\| Yes
	\|-		\|-
Line 98:		Line 98:
	=== Additional Information ===		=== Additional Information ===

		+	* [http://vadimtropashko.wordpress.com/2008/08/09/one-more-nested-intervals-vs-adjacency-list-comparison/ Good overview table of adjacency lists vs. Nested intervals]
	* [http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ Managing Hierarchical Data in MySQL]		* [http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ Managing Hierarchical Data in MySQL]
	* [http://www.sitepoint.com/hierarchical-data-database/ Storing Hierarchical Data in a Database]		* [http://www.sitepoint.com/hierarchical-data-database/ Storing Hierarchical Data in a Database]
		+	* [http://www.slideshare.net/billkarwin/models-for-hierarchical-data Slideshare .. Models for Hierarchical data]
		+	* [http://troels.arvin.dk/db/rdbms/links/#hierarchical More links on hierarchical data in SQL]

	== NOSQL ==		== NOSQL ==

Phylotastic

2012-05-16T20:25:25Z

Tasks => People:

← Older revision		Revision as of 20:25, 16 May 2012
(One intermediate revision not shown)
Line 15:		Line 15:
	* [[PhylotasticSandbox]] - for demos, mock-ups, etc		* [[PhylotasticSandbox]] - for demos, mock-ups, etc
	* [[PhylotasticSpec]] - for developing detailed specifications (includes '''scoping statements''')		* [[PhylotasticSpec]] - for developing detailed specifications (includes '''scoping statements''')
		+	* [[PhylotasticDatastore]] - for considering options for a Phylotastic data store

	== attention new participants! ==		== attention new participants! ==
Line 144:		Line 145:
	Indicate which tasks you are interested in working on, or add them if they aren't here!		Indicate which tasks you are interested in working on, or add them if they aren't here!

-	* Backend Tree Store: '''Jeet'''	+	* Backend Tree Store: '''Jeet''','''Jamie'''
	* Components		* Components
-	** Phylomatic-style Pruner: '''Jeet'''	+	** Phylomatic-style Pruner: '''Jeet''','''Jamie'''
	** TNRS: '''Jeet''', [[User:Gaurav\|Gaurav]]		** TNRS: '''Jeet''', [[User:Gaurav\|Gaurav]]
	** Branch Length Estimation: '''Jeet'''		** Branch Length Estimation: '''Jeet'''

PhylotasticDatastore

2012-05-16T20:21:12Z

Options for trees/hierarchies in RDMBS:

← Older revision		Revision as of 20:21, 16 May 2012
(8 intermediate revisions not shown)
Line 23:		Line 23:
	This documentation copied from [http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database options for storing hierarchical data in a relational database]		This documentation copied from [http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database options for storing hierarchical data in a relational database]

-	* Adjacency List:	+	* [http://en.wikipedia.org/wiki/Adjacency_list Adjacency List]:
	** Columns: ID, ParentID		** Columns: ID, ParentID
	** Easy to implement.		** Easy to implement.
Line 29:		Line 29:
	** Expensive to find level (can store as a computed column), ancestry & descendants (Bridge Hierarchy combined with level column can solve), path (Lineage Column can solve).		** Expensive to find level (can store as a computed column), ancestry & descendants (Bridge Hierarchy combined with level column can solve), path (Lineage Column can solve).
	** Use Common Table Expressions in those databases that support them to traverse.		** Use Common Table Expressions in those databases that support them to traverse.
-	* Nested Set (a.k.a Modified Preorder Tree Traversal)	+	* [http://en.wikipedia.org/wiki/Nested_set_model Nested Set] (a.k.a Modified Preorder Tree Traversal)
	**First described by Joe Celko - covered in depth in his book Trees and Hierarchies in SQL for Smarties		**First described by Joe Celko - covered in depth in his book Trees and Hierarchies in SQL for Smarties
	** Columns: Left, Right		** Columns: Left, Right
Line 35:		Line 35:
	** Compared to Adjacency List, moves, inserts, deletes more expensive.		** Compared to Adjacency List, moves, inserts, deletes more expensive.
	** Requires a specific sort order (e.g. created). So sorting all descendants in a different order requires additional work.		** Requires a specific sort order (e.g. created). So sorting all descendants in a different order requires additional work.
-	* Nested Intervals	+	* [https://communities.bmc.com/communities/docs/DOC-9902 Nested Intervals]
-	** Combination of Nested Sets and Materialized Path where left/right columns are floating point decimals instead of integers and encode the path information. In the later development of this idea nested intervals gave rise to matrix encoding.	+	** Combination of Nested Sets and Materialized Path where left/right columns are floating point decimals instead of integers and encode the path information. In the later development of this idea nested intervals gave rise to [http://vadimtropashko.files.wordpress.com/2011/07/ch5.pdf matrix encoding].
-	* Bridge Table (a.k.a. Closure Table: some good ideas about how to use triggers for maintaining this approach)	+	* [http://www.informationweek.com/news/219400252 Bridge Table] (a.k.a. [http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html Closure Table]: some good ideas about how to use triggers for maintaining this approach)
	** Columns: ancestor, descendant		** Columns: ancestor, descendant
	** Stands apart from table it describes.		** Stands apart from table it describes.
Line 43:		Line 43:
	** Cheap ancestry and descendants (albeit not in what order)		** Cheap ancestry and descendants (albeit not in what order)
	** For complete knowledge of a hierarchy needs to be combined with another option.		** For complete knowledge of a hierarchy needs to be combined with another option.
-	* Flat Table	+	* [http://evolt.org/node/4047/ Flat Table]
	** A modification of the Adjacency List that adds a Level and Rank (e.g. ordering) column to each record.		** A modification of the Adjacency List that adds a Level and Rank (e.g. ordering) column to each record.
	** Expensive move and delete		** Expensive move and delete
	** Cheap ancestry and descendants		** Cheap ancestry and descendants
	** Good Use: threaded discussion - forums / blog comments		** Good Use: threaded discussion - forums / blog comments
-	* Lineage Column (a.k.a. Materialized Path, Path Enumeration)	+	* [http://www.ferdychristant.com/blog//articles/DOMM-7QJPM7 Lineage Column] (a.k.a. [https://communities.bmc.com/communities/docs/DOC-9902 Materialized Path], Path Enumeration)
	** Column: lineage (e.g. /parent/child/grandchild/etc...)		** Column: lineage (e.g. /parent/child/grandchild/etc...)
	** Limit to how deep the hierarchy can be.		** Limit to how deep the hierarchy can be.
Line 54:		Line 54:
	** Ancestry tricky (database specific queries)		** Ancestry tricky (database specific queries)

-	=== ~~Additional Information~~ ===	+	=== RDBMS ===

-	* [http://~~mikehillyer~~.com/~~articles/managing~~-~~hierarchical~~-~~data~~-in-mysql/ ~~Managing Hierarchical Data in~~ MySQL]	+	{\| class="wikitable" style="text-align: left"
		+	! Feature
		+	! MySQL
		+	! PostgreSQL
		+	\|-
		+	\| Max allowed packet
		+	\| By default this is 1 MB but can be increased
		+	\|
		+	\|-
		+	\| Forced Referential integreity
		+	\| Yes ([http://www.sitepoint.com/mysql-innodb-table-pros-cons/ with InnoDB tables])
		+	\| Yes
		+	\|-
		+	\| Stored procedures
		+	\| Yes (> [http://dev.mysql.com/doc/refman/5.0/en/stored-routines.html MySQL 5.0]) However does not accept arrays (ie List of leaf nodes) as variables in stored procedures.
		+	\| Yes
		+	\|}

	=== Schema ===		=== Schema ===
Line 73:		Line 89:
	\|[http://www.ensembl.org/info/docs/api/compara/compara_schema.html EnsembleCompara]		\|[http://www.ensembl.org/info/docs/api/compara/compara_schema.html EnsembleCompara]
	\|PostgreSQL, MySQL		\|PostgreSQL, MySQL
-	\|No, but it is possible with ~~addition of~~ Chado tables.	+	\|No, but it is possible with [https://github.com/jestill/iplant-treerec/blob/master/schema/tr_schema_mysql.sql schema extensions] that add [http://gmod.org/wiki/Chado_CV_Module Chado controlled vocabulary tables].
	\|-		\|-
	\|[http://gmod.org/wiki/Chado_Phylogeny_Module Chado::Phylogeny ]		\|[http://gmod.org/wiki/Chado_Phylogeny_Module Chado::Phylogeny ]
Line 79:		Line 95:
	\|Yes (OBO, OWL with conversion to OBO)		\|Yes (OBO, OWL with conversion to OBO)
	\|}		\|}
		+
		+	=== Additional Information ===
		+
		+	* [http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ Managing Hierarchical Data in MySQL]
		+	* [http://www.sitepoint.com/hierarchical-data-database/ Storing Hierarchical Data in a Database]

	== NOSQL ==		== NOSQL ==

PhylotasticSchedule

2012-05-16T16:34:20Z

Day 1:

← Older revision		Revision as of 16:34, 16 May 2012
Line 46:		Line 46:
	* self-assembly of groups		* self-assembly of groups
	* reports from each group of its chosen goals		* reports from each group of its chosen goals
		+
		+	=== Session 5 (after dinner): Self-disassembly ===
		+
		+	'''The idea''': unwind, get to know fellow participants.
		+
		+	'''How to participate'''
		+	* go to

	== Day 2 ==		== Day 2 ==

PhylotasticUseCases

2012-05-16T16:17:15Z

Auto-supply species trees to reconcile-tree software:

← Older revision		Revision as of 16:17, 16 May 2012
Line 162:		Line 162:

	[[User:Arlin\|Arlin]] 15:24, 7 May 2012 (EDT)		[[User:Arlin\|Arlin]] 15:24, 7 May 2012 (EDT)
		+

	'''a pseudocode example''' for the case of a stand-alone tool that will discover a species phylogeny from the user's input data		'''a pseudocode example''' for the case of a stand-alone tool that will discover a species phylogeny from the user's input data
Line 175:		Line 176:
	*# get SPECIES_LIST from ID_LIST // uses NCBI's existing web-services interface		*# get SPECIES_LIST from ID_LIST // uses NCBI's existing web-services interface
	*# get PHYLOGENY for SPECIES_LIST (i.e., phylotastic)		*# get PHYLOGENY for SPECIES_LIST (i.e., phylotastic)
		+
		+
		+	'''Sequence string as input approach'''
		+
		+	As an alternative to taking a user gene tree as input, we may also consider input from a step back in the process, and think of going from a single input sequence to a fully reconciled gene tree. An excellent example of going from raw-sequence to a gene tree phylogeny is provided in the [http://dnasubway.iplantcollaborative.org/ DNA Subway] education platform. Currently the 'Prospect Genome' track on the DNA Subway halts at the generation of a gene tree. A phylotastic service could provide the species tree needed to take this one step further to a reconciled gene tree. The DNA Subway education platform could then go from a raw genome sequence to a set of reconciled gene trees for that genomic segment, and allow for educators to discuss the interpretation of orthologs and paralogs in genome evolution. --[[User:JamesEstill@gmail.com\|JamesEstill@gmail.com]] 12:17, 16 May 2012 (EDT)

	=== Teaching morphological evolution with reference to the community-consensus megatree of fishes. ===		=== Teaching morphological evolution with reference to the community-consensus megatree of fishes. ===

PhylotasticSchedule

2012-05-16T16:16:13Z

Day 2:

← Older revision		Revision as of 16:16, 16 May 2012
(One intermediate revision not shown)
Line 47:		Line 47:
	* reports from each group of its chosen goals		* reports from each group of its chosen goals

-	== ~~Days~~ 2, 3 and 4 ==	+	== Day 2 ==
		+
		+	'''Morning session''' 9:30 to 12:30
		+	* coffee breaks as needed
		+
		+	'''Lunch talk on iPlant's Discovery Environment''' (Naim Matasci)
		+	* lunch will be provided
		+
		+	'''Afternoon session''' 1:30 to 5:30
		+	* coffee breaks as needed
		+
		+	== Days 3 and 4 ==

	work, work, work, work, work, work, work, work, work the whole day through		work, work, work, work, work, work, work, work, work the whole day through
Line 55:		Line 66:

	'''Afternoon session''' 1:30 to 5:30		'''Afternoon session''' 1:30 to 5:30
-	* coffee breaks as needed	+	* coffee breaks as needed

	== Day 5 ==		== Day 5 ==

PhylotasticDatastore

2012-05-16T13:29:32Z

HBASE:

← Older revision		Revision as of 13:29, 16 May 2012
(2 intermediate revisions not shown)
Line 80:		Line 80:
	\|}		\|}

-	== NOSQL ~~Options~~ ==	+	== NOSQL ==

	Examples of [http://www.mongodb.org/display/DOCS/Trees+in+MongoDB storing trees in MongoDB].		Examples of [http://www.mongodb.org/display/DOCS/Trees+in+MongoDB storing trees in MongoDB].

	== Hadoop ==		== Hadoop ==
		+
		+	=== HBASE ===
		+
		+	HBase is an open-source, distributed, versioned, column-oriented store modeled after Google's Bigtable: A Distributed Storage System for Structured Data by Chang et al. Just as Bigtable leverages the distributed data storage provided by the Google File System, HBase provides Bigtable-like capabilities on top of Hadoop and HDFS.
		+
		+	* [https://hbase.apache.org/ Apache HBase Home]

	=== Tolomatic ===		=== Tolomatic ===