Biopython - User contributions [en]

BioGeography

2009-08-19T21:58:19Z

Matzke: /* Background: organization of Bio.Geography */

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

All classes and functions have been documented with standard docstrings. Code is available at the most recent github commit here: http://github.com/nmatzke/biopython/commits/Geography

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

Each class/function has been commented with docstrings. For latest commit, see: [http://github.com/nmatzke/biopython/commits/Geography http://github.com/nmatzke/biopython/commits/Geography].

==Tutorial==

Bio.Geography is a module for gathering and processing biogeographical data. The major motivation for the module is to assist analyses of evolutionary biogeography. A variety of inference algorithms are available for such analyses, such as [http://www.ebc.uu.se/systzoo/research/diva/manual/dmanual.html DIVA] and [http://code.google.com/p/lagrange/ lagrange]. The inputs to such programs are typically (a) a phylogeny and (b) the areas inhabited by the species at the tips of the phylogeny. A researcher who has gathered data on a particular group will likely have direct access to species location data, but many large-scale analyses may require gathering large amounts of occurrence data. Automated gathering/processing of occurrence data has a variety of other applications as well, including species mapping, niche modeling, error-checking of museum records, and monitoring range changes.

Occurrence data is derived mainly from museum collections. The major source of such data is the [http://www.gbif.org/ Global Biodiversity Information Facility] (GBIF). GBIF serves occurrence data recorded by hundreds of museums worldwide. GBIF occurrence data can be [http://data.gbif.org/occurrences/ searched manually], and results downloaded (see examples on GBIF website) in various formats: spreadsheet, Google Earth KML, or the XML DarwinCore format.

GBIF can also be accessed via an API. Bio.Geography can process manually downloaded DarwinCore results, or access GBIF directly.

===Background: organization of Bio.Geography===

It is useful to understand the overall organization of classes in Bio.Geography. There are four classes within the GbifXml module:

*'''GbifSearchResults''' -- Contains the methods for conducting a GBIF search, as well as attributes storing the results in different objects, depending on their stage of processing.
**Also contains summary statistics on the search (e.g., number of records found).
**The three objects which store results in different forms are '''GbifDarwincoreXmlString''', '''GbifXmlTree''', and a list of individual '''GbifObservationRecord''' objects.
**Method print_records for printing all contained records to screen.
* '''GbifDarwincoreXmlString''' -- Contains the raw text returned by GBIF. If output to a file, this would be a standard XML file adhering to the DarwinCore standard. Inherits from the standard python String class.
* '''GbifXmlTree''' -- Contains the ElementTree object which results from parsing GBIF's XML results. Also a number of methods for searching the ElementTree and finding matching elements, finding a certain element when it is contained within a certain larger element, etc.
* '''GbifObservationRecord''' -- Contains the attributes which may be found within a certain record, e.g. taxon, genus, species, latitude, longitude, etc., as well as functions for classifying a record into a certain geographical area, printing a record to screen, etc.
* '''TreeSum''' -- Contains functions and attributes for summarizing a phylogenetic tree, subsetting it, writing to screen, and calculating summary statistics.

===Parsing a local (manually downloaded) GBIF DarwinCore XML file===

For one-off uses of GBIF, you may find it easiest to just download occurrence data in spreadsheet format (for analysis) or KML (for mapping). But for analyses of many groups, or for repeatedly updating an analysis as new data is added to GBIF, automation is desirable.

A manual search conducted on the GBIF website can return results in the form of an XML file adhering to the [http://en.wikipedia.org/wiki/Darwin_Core DarwinCore] data standard. An example file can be found in biopython's Tests/Geography directory, with the name ''utric_search_v2.xml''. This file contains over 1000 occurrence records for ''Utricularia'', a genus of carnivorous plant.

Save the utric_search_v2.xml file in your working directory (or download a similar file from GBIF). Here are suggested steps to parse the file with Bio.Geography's GbifXml module. First, import the necessary classes and functions, and specify the filename of the input file.

<pre>
from Bio.Geography.GbifXml import GbifXmlTree, GbifSearchResults

from Bio.Geography.GeneralUtils import fix_ASCII_file

xml_fn = 'utric_search_v2.xml'
</pre>

Second, in order to display results to screen in python, we need to convert the file to plain ASCII (GBIF results contain all many of unusual characters from different languages, and no standardization of slanted quotes and the like; this can cause crashes when attempting to print to screen in python or ipython).

<pre>
xml_fn_new = fix_ASCII_file(xml_fn)
</pre>

This creates a new file with the string "_fixed.xml" added to the filename.

Next, we will parse the XML file into an ElementTree (a python object which contains the data from the XML file as a nested series of lists and dictionaries).

<pre>
from xml.etree import ElementTree as ET
xmltree = ET.parse(xml_fn_new)
</pre>

We can then store the element tree as an object of Class GbifXmlTree:

<pre>gbif_recs_xmltree = GbifXmlTree(xmltree)
</pre>

Then, with the xmltree stored, we parse it into individual records (stored in individual objects of class GbifObservationRecord), which are then stored as a group in an object of class GbifSearchResults.

<pre>recs = GbifSearchResults(gbif_recs_xmltree)
recs.extract_occurrences_from_gbif_xmltree(recs.gbif_recs_xmltree)
</pre>

The list of individual observation records can be accessed at recs.obs_recs_list. This will display the references to the first five records:

<pre>recs.obs_recs_list[0:4]
</pre>

To get the data for the first individual record:

<pre>rec = recs.obs_recs_list[0]

dir(rec)
</pre>

rec.lat will return the latitude, rec.long the longitude, etc. Certain data attributes are not found in all GBIF records; if they are missing, the field in question will contain "None".

To print all of the records in a tab-delimited table format:

<pre>
recs.print_records()
</pre>

===Checking how many matching records are hosted by GBIF===

Before we go through the trouble of downloading thousands of records, we may wish to know how many there are in GBIF first. The user must set up a dictionary containing the fields and search terms as keys and items, respectively. I.e.,

<pre>from GbifXml import GbifXmlTree, GbifSearchResults
params = {'format': 'darwin', 'scientificname': 'Genlisea*'}</pre>

"'format': 'darwin'" specifies that GBIF should return the results in DarwinCore format.

'scientificname' specifies the genus name to search on. Adding an '*' after the name will return anything that begins with "Genlisea".

The full list of search terms can be found on GBIF's [http://data.gbif.org/tutorial/services Occurrence record data service], which is linked from the [http://data.gbif.org/tutorial/services Using data from the GBIF portal].

Once you have specified your search parameters, initiate a new GbifSearchResults object and run get_numhits to get the number of hits:

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
recs = GbifSearchResults()
numhits = recs.get_numhits(params)</pre>

As of August 2009, 169 matching records existed in GBIF matching "Genlisea*"

For constrast, run the same search ''without'' the asterisk ('*'):

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea'}
numhits = recs.get_numhits(params)</pre>

We only get ~10 results -- presumably records of specimens only identified down to genus and no further.

===Downloading an individual record===

Individual records can be downloaded by key. To download an individual record:

<pre>
rec = recs.obs_recs_list[0]
key = rec.gbifkey
# (or manually)
# key = 175067484
xmlrec = recs.get_record(key)
print xmlrec</pre>

If you want to print the xmlrec ElementTree object, store xmlrec in a GbifXmlTree object and run print_xmltree:

<pre>GbifXmlTree(xmlrec).print_xmltree()</pre>

===Summary statistics for phylogenetic trees with TreeSum===

Biogeographical regions are often characterized by alpha and beta-diversity statistics: basically, these are indices of the number of species found within or between regions. Given a phylogeny for organisms in a region, phylogenetic alpha- and beta-diversity statistics can be calculated. This has been implemented in a thorough way in the [http://www.phylodiversity.net/phylocom/ phylocom package] by Webb et al., but for some purposes it is useful to calculate the statistics directly in python.

Here, we need to start with a Newick tree string:

<pre>trstr2 = "(((t9:0.385832, (t8:0.445135,t4:0.41401)C:0.024032)B:0.041436, t6:0.392496)A:0.0291131, t2:0.497673, ((t0:0.301171, t7:0.482152)E:0.0268148, ((t5:0.0984167,t3:0.488578)G:0.0349662, t1:0.130208)F:0.0318288)D:0.0273876);"

to2 = Tree(trstr2)</pre>

Then, we create a tree summary object:

<pre>ts = TreeSum(to2)</pre>

The function test_Tree will run the metrics (MPD = Mean Phylogenetic Distance, NRI = Net Relatedness Index, MNPD = Mean Nearest Neighbor Phylogenetic Distance, NTI = Nearest Taxon Index, PD = total Phylogenetic distance) and output to screen:

<pre>ts.test_Tree()</pre>

By subsetting a tree to taxa only existing within a region, statistics can be calculated by region.

===Downloading and processing large numbers of records===

GBIF only allows a maximum of 1000 observation records to be downloaded at a time (10,000 for KML records). To get more, we need to download and process them in stages.

Again we will set up our parameters dictionary, and also an "inc" variable to specify the number of records to download per server request.

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
inc = 100
recs3 = GbifSearchResults()
gbif_xmltree_list = recs3.get_all_records_by_increment(params, inc)
</pre>

As with biopython's interactions with NCBI servers, the GbifSearchResults module keeps track of when the last GBIF request was made, and requires a 3-second wait before a new request.

Each server request returns an XML string; these are parsed into GbifXmlTree objects, and a list of the returned GbifXmlTree objects is returned to gbif_xmltree_list. The individual records have also been parsed:

<pre>
recs3.print_records()
</pre>

===Classifying records into geographical regions===

Biogeographical analyses will often require that you determine what area(s) a taxon lives in. Areas are not always obviously delineated, and analysts may wish to try several different possible sets of areas and see how this influences their analysis.

Below, we set up a polygon containing the latitude/longitude coordinates for the Northern Hemisphere, and then set the "area" attribute for each matching record to "NorthernHemisphere":

<pre>
ul = (-180, 90)
ur = (180, 90)
ll = (-180, 0)
lr = (180, 0)
poly = [ul, ur, ll, lr]
polyname = "NorthernHemisphere"

recs3.print_records()
</pre>

This process can be repeated for all polygons of interest until all GBIF records have been classified (except for GBIF records which lacked lat/long data in the first place, which sometimes happens).

GeogUtils also contains open access libraries for processing shapefile/dbf files -- these are standard GIS file formats, and various publicly-accessible shapefiles might serve as sources for polygons.

Warning: the point-in-polygon operation will fail dramatically if your polygon crosses the International Dateline. The best solution in this case is to split any polygons crossing the dateline into two polygons, one on each side of the line.

===General notes===

GBIF search results often contain non-ASCII characters (e.g. international placenames) and other confusing items, e.g., web links in angle brackets, which can be misinterpreted as unmatched XML tags if a GBIF search result is read to ASCII and then an attempt is made to parse it.

In general, the Geography module will handle things fine if the results are being processed in the background; but to print results to screen, a series of functions from GeneralUtils are used to convert a string to plain ASCII. This avoids crashes e.g. when printing data to screen. Therefore, these printed-to-screen results may slightly alter the content of the original search results.

BioGeography

2009-08-19T21:50:06Z

Matzke: /* Background: organization of Bio.Geography */

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

All classes and functions have been documented with standard docstrings. Code is available at the most recent github commit here: http://github.com/nmatzke/biopython/commits/Geography

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

Each class/function has been commented with docstrings. For latest commit, see: [http://github.com/nmatzke/biopython/commits/Geography http://github.com/nmatzke/biopython/commits/Geography].

==Tutorial==

Bio.Geography is a module for gathering and processing biogeographical data. The major motivation for the module is to assist analyses of evolutionary biogeography. A variety of inference algorithms are available for such analyses, such as [http://www.ebc.uu.se/systzoo/research/diva/manual/dmanual.html DIVA] and [http://code.google.com/p/lagrange/ lagrange]. The inputs to such programs are typically (a) a phylogeny and (b) the areas inhabited by the species at the tips of the phylogeny. A researcher who has gathered data on a particular group will likely have direct access to species location data, but many large-scale analyses may require gathering large amounts of occurrence data. Automated gathering/processing of occurrence data has a variety of other applications as well, including species mapping, niche modeling, error-checking of museum records, and monitoring range changes.

Occurrence data is derived mainly from museum collections. The major source of such data is the [http://www.gbif.org/ Global Biodiversity Information Facility] (GBIF). GBIF serves occurrence data recorded by hundreds of museums worldwide. GBIF occurrence data can be [http://data.gbif.org/occurrences/ searched manually], and results downloaded (see examples on GBIF website) in various formats: spreadsheet, Google Earth KML, or the XML DarwinCore format.

GBIF can also be accessed via an API. Bio.Geography can process manually downloaded DarwinCore results, or access GBIF directly.

===Background: organization of Bio.Geography===

It is useful to understand the overall organization of classes in Bio.Geography. There are four classes within the GbifXml module:

*'''GbifSearchResults''' -- Contains the methods for conducting a GBIF search, as well as attributes storing the results in different objects, depending on their stage of processing.
**Also contains summary statistics on the search (e.g., number of records found).
**The three objects which store results in different forms are '''GbifDarwincoreXmlString''', '''GbifXmlTree''', and a list of individual '''GbifObservationRecord''' objects.
**Method print_records for printing all contained records to screen.
* '''GbifDarwincoreXmlString''' -- Contains the raw text returned by GBIF. If output to a file, this would be a standard XML file adhering to the DarwinCore standard. Inherits from the standard python String class.
* '''GbifXmlTree''' -- Contains the ElementTree object which results from parsing GBIF's XML results. Also a number of methods for searching the ElementTree and finding matching elements, finding a certain element when it is contained within a certain larger element, etc.
* '''GbifObservationRecord''' -- Contains the attributes which may be found within a certain record, e.g. taxon, genus, species, latitude, longitude, etc., as well as functions for classifying a record into a certain geographical area, printing a record to screen, etc.

===Parsing a local (manually downloaded) GBIF DarwinCore XML file===

For one-off uses of GBIF, you may find it easiest to just download occurrence data in spreadsheet format (for analysis) or KML (for mapping). But for analyses of many groups, or for repeatedly updating an analysis as new data is added to GBIF, automation is desirable.

A manual search conducted on the GBIF website can return results in the form of an XML file adhering to the [http://en.wikipedia.org/wiki/Darwin_Core DarwinCore] data standard. An example file can be found in biopython's Tests/Geography directory, with the name ''utric_search_v2.xml''. This file contains over 1000 occurrence records for ''Utricularia'', a genus of carnivorous plant.

Save the utric_search_v2.xml file in your working directory (or download a similar file from GBIF). Here are suggested steps to parse the file with Bio.Geography's GbifXml module. First, import the necessary classes and functions, and specify the filename of the input file.

<pre>
from Bio.Geography.GbifXml import GbifXmlTree, GbifSearchResults

from Bio.Geography.GeneralUtils import fix_ASCII_file

xml_fn = 'utric_search_v2.xml'
</pre>

Second, in order to display results to screen in python, we need to convert the file to plain ASCII (GBIF results contain all many of unusual characters from different languages, and no standardization of slanted quotes and the like; this can cause crashes when attempting to print to screen in python or ipython).

<pre>
xml_fn_new = fix_ASCII_file(xml_fn)
</pre>

This creates a new file with the string "_fixed.xml" added to the filename.

Next, we will parse the XML file into an ElementTree (a python object which contains the data from the XML file as a nested series of lists and dictionaries).

<pre>
from xml.etree import ElementTree as ET
xmltree = ET.parse(xml_fn_new)
</pre>

We can then store the element tree as an object of Class GbifXmlTree:

<pre>gbif_recs_xmltree = GbifXmlTree(xmltree)
</pre>

Then, with the xmltree stored, we parse it into individual records (stored in individual objects of class GbifObservationRecord), which are then stored as a group in an object of class GbifSearchResults.

<pre>recs = GbifSearchResults(gbif_recs_xmltree)
recs.extract_occurrences_from_gbif_xmltree(recs.gbif_recs_xmltree)
</pre>

The list of individual observation records can be accessed at recs.obs_recs_list. This will display the references to the first five records:

<pre>recs.obs_recs_list[0:4]
</pre>

To get the data for the first individual record:

<pre>rec = recs.obs_recs_list[0]

dir(rec)
</pre>

rec.lat will return the latitude, rec.long the longitude, etc. Certain data attributes are not found in all GBIF records; if they are missing, the field in question will contain "None".

To print all of the records in a tab-delimited table format:

<pre>
recs.print_records()
</pre>

===Checking how many matching records are hosted by GBIF===

Before we go through the trouble of downloading thousands of records, we may wish to know how many there are in GBIF first. The user must set up a dictionary containing the fields and search terms as keys and items, respectively. I.e.,

<pre>from GbifXml import GbifXmlTree, GbifSearchResults
params = {'format': 'darwin', 'scientificname': 'Genlisea*'}</pre>

"'format': 'darwin'" specifies that GBIF should return the results in DarwinCore format.

'scientificname' specifies the genus name to search on. Adding an '*' after the name will return anything that begins with "Genlisea".

The full list of search terms can be found on GBIF's [http://data.gbif.org/tutorial/services Occurrence record data service], which is linked from the [http://data.gbif.org/tutorial/services Using data from the GBIF portal].

Once you have specified your search parameters, initiate a new GbifSearchResults object and run get_numhits to get the number of hits:

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
recs = GbifSearchResults()
numhits = recs.get_numhits(params)</pre>

As of August 2009, 169 matching records existed in GBIF matching "Genlisea*"

For constrast, run the same search ''without'' the asterisk ('*'):

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea'}
numhits = recs.get_numhits(params)</pre>

We only get ~10 results -- presumably records of specimens only identified down to genus and no further.

===Downloading an individual record===

Individual records can be downloaded by key. To download an individual record:

<pre>
rec = recs.obs_recs_list[0]
key = rec.gbifkey
# (or manually)
# key = 175067484
xmlrec = recs.get_record(key)
print xmlrec</pre>

If you want to print the xmlrec ElementTree object, store xmlrec in a GbifXmlTree object and run print_xmltree:

<pre>GbifXmlTree(xmlrec).print_xmltree()</pre>

===Summary statistics for phylogenetic trees with TreeSum===

Biogeographical regions are often characterized by alpha and beta-diversity statistics: basically, these are indices of the number of species found within or between regions. Given a phylogeny for organisms in a region, phylogenetic alpha- and beta-diversity statistics can be calculated. This has been implemented in a thorough way in the [http://www.phylodiversity.net/phylocom/ phylocom package] by Webb et al., but for some purposes it is useful to calculate the statistics directly in python.

Here, we need to start with a Newick tree string:

<pre>trstr2 = "(((t9:0.385832, (t8:0.445135,t4:0.41401)C:0.024032)B:0.041436, t6:0.392496)A:0.0291131, t2:0.497673, ((t0:0.301171, t7:0.482152)E:0.0268148, ((t5:0.0984167,t3:0.488578)G:0.0349662, t1:0.130208)F:0.0318288)D:0.0273876);"

to2 = Tree(trstr2)</pre>

Then, we create a tree summary object:

<pre>ts = TreeSum(to2)</pre>

The function test_Tree will run the metrics (MPD = Mean Phylogenetic Distance, NRI = Net Relatedness Index, MNPD = Mean Nearest Neighbor Phylogenetic Distance, NTI = Nearest Taxon Index, PD = total Phylogenetic distance) and output to screen:

<pre>ts.test_Tree()</pre>

By subsetting a tree to taxa only existing within a region, statistics can be calculated by region.

===Downloading and processing large numbers of records===

GBIF only allows a maximum of 1000 observation records to be downloaded at a time (10,000 for KML records). To get more, we need to download and process them in stages.

Again we will set up our parameters dictionary, and also an "inc" variable to specify the number of records to download per server request.

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
inc = 100
recs3 = GbifSearchResults()
gbif_xmltree_list = recs3.get_all_records_by_increment(params, inc)
</pre>

As with biopython's interactions with NCBI servers, the GbifSearchResults module keeps track of when the last GBIF request was made, and requires a 3-second wait before a new request.

Each server request returns an XML string; these are parsed into GbifXmlTree objects, and a list of the returned GbifXmlTree objects is returned to gbif_xmltree_list. The individual records have also been parsed:

<pre>
recs3.print_records()
</pre>

===Classifying records into geographical regions===

Biogeographical analyses will often require that you determine what area(s) a taxon lives in. Areas are not always obviously delineated, and analysts may wish to try several different possible sets of areas and see how this influences their analysis.

Below, we set up a polygon containing the latitude/longitude coordinates for the Northern Hemisphere, and then set the "area" attribute for each matching record to "NorthernHemisphere":

<pre>
ul = (-180, 90)
ur = (180, 90)
ll = (-180, 0)
lr = (180, 0)
poly = [ul, ur, ll, lr]
polyname = "NorthernHemisphere"

recs3.print_records()
</pre>

This process can be repeated for all polygons of interest until all GBIF records have been classified (except for GBIF records which lacked lat/long data in the first place, which sometimes happens).

GeogUtils also contains open access libraries for processing shapefile/dbf files -- these are standard GIS file formats, and various publicly-accessible shapefiles might serve as sources for polygons.

Warning: the point-in-polygon operation will fail dramatically if your polygon crosses the International Dateline. The best solution in this case is to split any polygons crossing the dateline into two polygons, one on each side of the line.

===General notes===

GBIF search results often contain non-ASCII characters (e.g. international placenames) and other confusing items, e.g., web links in angle brackets, which can be misinterpreted as unmatched XML tags if a GBIF search result is read to ASCII and then an attempt is made to parse it.

In general, the Geography module will handle things fine if the results are being processed in the background; but to print results to screen, a series of functions from GeneralUtils are used to convert a string to plain ASCII. This avoids crashes e.g. when printing data to screen. Therefore, these printed-to-screen results may slightly alter the content of the original search results.

BioGeography

2009-08-19T21:49:13Z

Matzke: /* Parsing a local (manually downloaded) GBIF DarwinCore XML file */

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

All classes and functions have been documented with standard docstrings. Code is available at the most recent github commit here: http://github.com/nmatzke/biopython/commits/Geography

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

Each class/function has been commented with docstrings. For latest commit, see: [http://github.com/nmatzke/biopython/commits/Geography http://github.com/nmatzke/biopython/commits/Geography].

==Tutorial==

Bio.Geography is a module for gathering and processing biogeographical data. The major motivation for the module is to assist analyses of evolutionary biogeography. A variety of inference algorithms are available for such analyses, such as [http://www.ebc.uu.se/systzoo/research/diva/manual/dmanual.html DIVA] and [http://code.google.com/p/lagrange/ lagrange]. The inputs to such programs are typically (a) a phylogeny and (b) the areas inhabited by the species at the tips of the phylogeny. A researcher who has gathered data on a particular group will likely have direct access to species location data, but many large-scale analyses may require gathering large amounts of occurrence data. Automated gathering/processing of occurrence data has a variety of other applications as well, including species mapping, niche modeling, error-checking of museum records, and monitoring range changes.

Occurrence data is derived mainly from museum collections. The major source of such data is the [http://www.gbif.org/ Global Biodiversity Information Facility] (GBIF). GBIF serves occurrence data recorded by hundreds of museums worldwide. GBIF occurrence data can be [http://data.gbif.org/occurrences/ searched manually], and results downloaded (see examples on GBIF website) in various formats: spreadsheet, Google Earth KML, or the XML DarwinCore format.

GBIF can also be accessed via an API. Bio.Geography can process manually downloaded DarwinCore results, or access GBIF directly.

===Background: organization of Bio.Geography===

It is useful to understand the overall organization of classes in Bio.Geography. There are four classes within the GbifXml module:

*GbifSearchResults -- Contains the methods for conducting a GBIF search, as well as attributes storing the results in different objects, depending on their stage of processing.
**Also contains summary statistics on the search (e.g., number of records found).
**The three objects which store results in different forms are GbifDarwincoreXmlString, GbifXmlTree, and a list of individual GbifObservationRecord objects.
**Method print_records for printing all contained records to screen.
* GbifDarwincoreXmlString -- Contains the raw text returned by GBIF. If output to a file, this would be a standard XML file adhering to the DarwinCore standard. Inherits from the standard python String class.
* GbifXmlTree -- Contains the ElementTree object which results from parsing GBIF's XML results. Also a number of methods for searching the ElementTree and finding matching elements, finding a certain element when it is contained within a certain larger element, etc.
* GbifObservationRecord -- Contains the attributes which may be found within a certain record, e.g. taxon, genus, species, latitude, longitude, etc., as well as functions for classifying a record into a certain geographical area, printing a record to screen, etc.

===Parsing a local (manually downloaded) GBIF DarwinCore XML file===

For one-off uses of GBIF, you may find it easiest to just download occurrence data in spreadsheet format (for analysis) or KML (for mapping). But for analyses of many groups, or for repeatedly updating an analysis as new data is added to GBIF, automation is desirable.

A manual search conducted on the GBIF website can return results in the form of an XML file adhering to the [http://en.wikipedia.org/wiki/Darwin_Core DarwinCore] data standard. An example file can be found in biopython's Tests/Geography directory, with the name ''utric_search_v2.xml''. This file contains over 1000 occurrence records for ''Utricularia'', a genus of carnivorous plant.

Save the utric_search_v2.xml file in your working directory (or download a similar file from GBIF). Here are suggested steps to parse the file with Bio.Geography's GbifXml module. First, import the necessary classes and functions, and specify the filename of the input file.

<pre>
from Bio.Geography.GbifXml import GbifXmlTree, GbifSearchResults

from Bio.Geography.GeneralUtils import fix_ASCII_file

xml_fn = 'utric_search_v2.xml'
</pre>

Second, in order to display results to screen in python, we need to convert the file to plain ASCII (GBIF results contain all many of unusual characters from different languages, and no standardization of slanted quotes and the like; this can cause crashes when attempting to print to screen in python or ipython).

<pre>
xml_fn_new = fix_ASCII_file(xml_fn)
</pre>

This creates a new file with the string "_fixed.xml" added to the filename.

Next, we will parse the XML file into an ElementTree (a python object which contains the data from the XML file as a nested series of lists and dictionaries).

<pre>
from xml.etree import ElementTree as ET
xmltree = ET.parse(xml_fn_new)
</pre>

We can then store the element tree as an object of Class GbifXmlTree:

<pre>gbif_recs_xmltree = GbifXmlTree(xmltree)
</pre>

Then, with the xmltree stored, we parse it into individual records (stored in individual objects of class GbifObservationRecord), which are then stored as a group in an object of class GbifSearchResults.

<pre>recs = GbifSearchResults(gbif_recs_xmltree)
recs.extract_occurrences_from_gbif_xmltree(recs.gbif_recs_xmltree)
</pre>

The list of individual observation records can be accessed at recs.obs_recs_list. This will display the references to the first five records:

<pre>recs.obs_recs_list[0:4]
</pre>

To get the data for the first individual record:

<pre>rec = recs.obs_recs_list[0]

dir(rec)
</pre>

rec.lat will return the latitude, rec.long the longitude, etc. Certain data attributes are not found in all GBIF records; if they are missing, the field in question will contain "None".

To print all of the records in a tab-delimited table format:

<pre>
recs.print_records()
</pre>

===Checking how many matching records are hosted by GBIF===

Before we go through the trouble of downloading thousands of records, we may wish to know how many there are in GBIF first. The user must set up a dictionary containing the fields and search terms as keys and items, respectively. I.e.,

<pre>from GbifXml import GbifXmlTree, GbifSearchResults
params = {'format': 'darwin', 'scientificname': 'Genlisea*'}</pre>

"'format': 'darwin'" specifies that GBIF should return the results in DarwinCore format.

'scientificname' specifies the genus name to search on. Adding an '*' after the name will return anything that begins with "Genlisea".

The full list of search terms can be found on GBIF's [http://data.gbif.org/tutorial/services Occurrence record data service], which is linked from the [http://data.gbif.org/tutorial/services Using data from the GBIF portal].

Once you have specified your search parameters, initiate a new GbifSearchResults object and run get_numhits to get the number of hits:

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
recs = GbifSearchResults()
numhits = recs.get_numhits(params)</pre>

As of August 2009, 169 matching records existed in GBIF matching "Genlisea*"

For constrast, run the same search ''without'' the asterisk ('*'):

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea'}
numhits = recs.get_numhits(params)</pre>

We only get ~10 results -- presumably records of specimens only identified down to genus and no further.

===Downloading an individual record===

Individual records can be downloaded by key. To download an individual record:

<pre>
rec = recs.obs_recs_list[0]
key = rec.gbifkey
# (or manually)
# key = 175067484
xmlrec = recs.get_record(key)
print xmlrec</pre>

If you want to print the xmlrec ElementTree object, store xmlrec in a GbifXmlTree object and run print_xmltree:

<pre>GbifXmlTree(xmlrec).print_xmltree()</pre>

===Summary statistics for phylogenetic trees with TreeSum===

Biogeographical regions are often characterized by alpha and beta-diversity statistics: basically, these are indices of the number of species found within or between regions. Given a phylogeny for organisms in a region, phylogenetic alpha- and beta-diversity statistics can be calculated. This has been implemented in a thorough way in the [http://www.phylodiversity.net/phylocom/ phylocom package] by Webb et al., but for some purposes it is useful to calculate the statistics directly in python.

Here, we need to start with a Newick tree string:

<pre>trstr2 = "(((t9:0.385832, (t8:0.445135,t4:0.41401)C:0.024032)B:0.041436, t6:0.392496)A:0.0291131, t2:0.497673, ((t0:0.301171, t7:0.482152)E:0.0268148, ((t5:0.0984167,t3:0.488578)G:0.0349662, t1:0.130208)F:0.0318288)D:0.0273876);"

to2 = Tree(trstr2)</pre>

Then, we create a tree summary object:

<pre>ts = TreeSum(to2)</pre>

The function test_Tree will run the metrics (MPD = Mean Phylogenetic Distance, NRI = Net Relatedness Index, MNPD = Mean Nearest Neighbor Phylogenetic Distance, NTI = Nearest Taxon Index, PD = total Phylogenetic distance) and output to screen:

<pre>ts.test_Tree()</pre>

By subsetting a tree to taxa only existing within a region, statistics can be calculated by region.

===Downloading and processing large numbers of records===

GBIF only allows a maximum of 1000 observation records to be downloaded at a time (10,000 for KML records). To get more, we need to download and process them in stages.

Again we will set up our parameters dictionary, and also an "inc" variable to specify the number of records to download per server request.

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
inc = 100
recs3 = GbifSearchResults()
gbif_xmltree_list = recs3.get_all_records_by_increment(params, inc)
</pre>

As with biopython's interactions with NCBI servers, the GbifSearchResults module keeps track of when the last GBIF request was made, and requires a 3-second wait before a new request.

Each server request returns an XML string; these are parsed into GbifXmlTree objects, and a list of the returned GbifXmlTree objects is returned to gbif_xmltree_list. The individual records have also been parsed:

<pre>
recs3.print_records()
</pre>

===Classifying records into geographical regions===

Biogeographical analyses will often require that you determine what area(s) a taxon lives in. Areas are not always obviously delineated, and analysts may wish to try several different possible sets of areas and see how this influences their analysis.

Below, we set up a polygon containing the latitude/longitude coordinates for the Northern Hemisphere, and then set the "area" attribute for each matching record to "NorthernHemisphere":

<pre>
ul = (-180, 90)
ur = (180, 90)
ll = (-180, 0)
lr = (180, 0)
poly = [ul, ur, ll, lr]
polyname = "NorthernHemisphere"

recs3.print_records()
</pre>

This process can be repeated for all polygons of interest until all GBIF records have been classified (except for GBIF records which lacked lat/long data in the first place, which sometimes happens).

GeogUtils also contains open access libraries for processing shapefile/dbf files -- these are standard GIS file formats, and various publicly-accessible shapefiles might serve as sources for polygons.

Warning: the point-in-polygon operation will fail dramatically if your polygon crosses the International Dateline. The best solution in this case is to split any polygons crossing the dateline into two polygons, one on each side of the line.

===General notes===

GBIF search results often contain non-ASCII characters (e.g. international placenames) and other confusing items, e.g., web links in angle brackets, which can be misinterpreted as unmatched XML tags if a GBIF search result is read to ASCII and then an attempt is made to parse it.

In general, the Geography module will handle things fine if the results are being processed in the background; but to print results to screen, a series of functions from GeneralUtils are used to convert a string to plain ASCII. This avoids crashes e.g. when printing data to screen. Therefore, these printed-to-screen results may slightly alter the content of the original search results.

BioGeography

2009-08-19T08:57:31Z

Matzke: /* Summary of functions */

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

All classes and functions have been documented with standard docstrings. Code is available at the most recent github commit here: http://github.com/nmatzke/biopython/commits/Geography

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

Each class/function has been commented with docstrings. For latest commit, see: [http://github.com/nmatzke/biopython/commits/Geography http://github.com/nmatzke/biopython/commits/Geography].

==Tutorial==

Bio.Geography is a module for gathering and processing biogeographical data. The major motivation for the module is to assist analyses of evolutionary biogeography. A variety of inference algorithms are available for such analyses, such as [http://www.ebc.uu.se/systzoo/research/diva/manual/dmanual.html DIVA] and [http://code.google.com/p/lagrange/ lagrange]. The inputs to such programs are typically (a) a phylogeny and (b) the areas inhabited by the species at the tips of the phylogeny. A researcher who has gathered data on a particular group will likely have direct access to species location data, but many large-scale analyses may require gathering large amounts of occurrence data. Automated gathering/processing of occurrence data has a variety of other applications as well, including species mapping, niche modeling, error-checking of museum records, and monitoring range changes.

Occurrence data is derived mainly from museum collections. The major source of such data is the [http://www.gbif.org/ Global Biodiversity Information Facility] (GBIF). GBIF serves occurrence data recorded by hundreds of museums worldwide. GBIF occurrence data can be [http://data.gbif.org/occurrences/ searched manually], and results downloaded (see examples on GBIF website) in various formats: spreadsheet, Google Earth KML, or the XML DarwinCore format.

GBIF can also be accessed via an API. Bio.Geography can process manually downloaded DarwinCore results, or access GBIF directly.

===Parsing a local (manually downloaded) GBIF DarwinCore XML file===

For one-off uses of GBIF, you may find it easiest to just download occurrence data in spreadsheet format (for analysis) or KML (for mapping). But for analyses of many groups, or for repeatedly updating an analysis as new data is added to GBIF, automation is desirable.

A manual search conducted on the GBIF website can return results in the form of an XML file adhering to the [http://en.wikipedia.org/wiki/Darwin_Core DarwinCore] data standard. An example file can be found in biopython's Tests/Geography directory, with the name ''utric_search_v2.xml''. This file contains over 1000 occurrence records for ''Utricularia'', a genus of carnivorous plant.

Save the utric_search_v2.xml file in your working directory (or download a similar file from GBIF). Here are suggested steps to parse the file with Bio.Geography's GbifXml module:

<pre>
from Bio.Geography.GbifXml import GbifXmlTree, GbifSearchResults

from Bio.Geography.GeneralUtils import fix_ASCII_file

xml_fn = 'utric_search_v2.xml'
</pre>

First, in order to display results to screen in python, we need to convert the file to plain ASCII (GBIF results contain all many of unusual characters from different languages, and no standardization of slanted quotes and the like; this can cause crashes when attempting to print to screen in python).

<pre>
xml_fn_new = fix_ASCII_file(xml_fn)
</pre>

This creates a new file with the string "_fixed.xml" added to the filename.

Next, we will parse the XML file into an ElementTree (a python object which contains the data from the XML file as a nested series of lists and dictionaries).

<pre>
from xml.etree import ElementTree as ET
xmltree = ET.parse(xml_fn_new)
</pre>

We can then store the element tree as nn object of Class GbifXmlTree:

<pre>gbif_recs_xmltree = GbifXmlTree(xmltree)
</pre>

Then, with the xmltree stored, we parse it into individual records (stored in individual objects of class GbifObservationRecord), which are then stored as a group in an object of class GbifSearchResults.

<pre>recs = GbifSearchResults(gbif_recs_xmltree)
recs.extract_occurrences_from_gbif_xmltree(recs.gbif_recs_xmltree)
</pre>

The list of individual observation records can be accessed at recs.obs_recs_list:

<pre>recs.obs_recs_list[0:4]
</pre>

To get the data for the first individual record:

<pre>rec = recs.obs_recs_list[0]

dir(rec)
</pre>

rec.lat will return the latitude, rec.long the longitude, etc. Certain data attributes are not found in all GBIF records; if they are missing, the field in question will contain "None".

To print all of the records in a tab-delimited table format:

<pre>
recs.print_records()
</pre>

===Checking how many matching records are hosted by GBIF===

Before we go through the trouble of downloading thousands of records, we may wish to know how many there are in GBIF first. The user must set up a dictionary containing the fields and search terms as keys and items, respectively. I.e.,

<pre>from GbifXml import GbifXmlTree, GbifSearchResults
params = {'format': 'darwin', 'scientificname': 'Genlisea*'}</pre>

"'format': 'darwin'" specifies that GBIF should return the results in DarwinCore format.

'scientificname' specifies the genus name to search on. Adding an '*' after the name will return anything that begins with "Genlisea".

The full list of search terms can be found on GBIF's [http://data.gbif.org/tutorial/services Occurrence record data service], which is linked from the [http://data.gbif.org/tutorial/services Using data from the GBIF portal].

Once you have specified your search parameters, initiate a new GbifSearchResults object and run get_numhits to get the number of hits:

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
recs = GbifSearchResults()
numhits = recs.get_numhits(params)</pre>

As of August 2009, 169 matching records existed in GBIF matching "Genlisea*"

For constrast, run the same search ''without'' the asterisk ('*'):

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea'}
numhits = recs.get_numhits(params)</pre>

We only get ~10 results -- presumably records of specimens only identified down to genus and no further.

===Downloading an individual record===

Individual records can be downloaded by key. To download an individual record:

<pre>
rec = recs.obs_recs_list[0]
key = rec.gbifkey
# (or manually)
# key = 175067484
xmlrec = recs.get_record(key)
print xmlrec</pre>

If you want to print the xmlrec ElementTree object, store xmlrec in a GbifXmlTree object and run print_xmltree:

<pre>GbifXmlTree(xmlrec).print_xmltree()</pre>

===Summary statistics for phylogenetic trees with TreeSum===

Biogeographical regions are often characterized by alpha and beta-diversity statistics: basically, these are indices of the number of species found within or between regions. Given a phylogeny for organisms in a region, phylogenetic alpha- and beta-diversity statistics can be calculated. This has been implemented in a thorough way in the [http://www.phylodiversity.net/phylocom/ phylocom package] by Webb et al., but for some purposes it is useful to calculate the statistics directly in python.

Here, we need to start with a Newick tree string:

<pre>trstr2 = "(((t9:0.385832, (t8:0.445135,t4:0.41401)C:0.024032)B:0.041436, t6:0.392496)A:0.0291131, t2:0.497673, ((t0:0.301171, t7:0.482152)E:0.0268148, ((t5:0.0984167,t3:0.488578)G:0.0349662, t1:0.130208)F:0.0318288)D:0.0273876);"

to2 = Tree(trstr2)</pre>

Then, we create a tree summary object:

<pre>ts = TreeSum(to2)</pre>

The function test_Tree will run the metrics (MPD = Mean Phylogenetic Distance, NRI = Net Relatedness Index, MNPD = Mean Nearest Neighbor Phylogenetic Distance, NTI = Nearest Taxon Index, PD = total Phylogenetic distance) and output to screen:

<pre>ts.test_Tree()</pre>

By subsetting a tree to taxa only existing within a region, statistics can be calculated by region.

===Downloading and processing large numbers of records===

GBIF only allows a maximum of 1000 observation records to be downloaded at a time (10,000 for KML records). To get more, we need to download and process them in stages.

Again we will set up our parameters dictionary, and also an "inc" variable to specify the number of records to download per server request.

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
inc = 100
recs3 = GbifSearchResults()
gbif_xmltree_list = recs3.get_all_records_by_increment(params, inc)
</pre>

As with biopython's interactions with NCBI servers, the GbifSearchResults module keeps track of when the last GBIF request was made, and requires a 3-second wait before a new request.

Each server request returns an XML string; these are parsed into GbifXmlTree objects, and a list of the returned GbifXmlTree objects is returned to gbif_xmltree_list. The individual records have also been parsed:

<pre>
recs3.print_records()
</pre>

===Classifying records into geographical regions===

Biogeographical analyses will often require that you determine what area(s) a taxon lives in. Areas are not always obviously delineated, and analysts may wish to try several different possible sets of areas and see how this influences their analysis.

Below, we set up a polygon containing the latitude/longitude coordinates for the Northern Hemisphere, and then set the "area" attribute for each matching record to "NorthernHemisphere":

<pre>
ul = (-180, 90)
ur = (180, 90)
ll = (-180, 0)
lr = (180, 0)
poly = [ul, ur, ll, lr]
polyname = "NorthernHemisphere"

recs3.print_records()
</pre>

This process can be repeated for all polygons of interest until all GBIF records have been classified (except for GBIF records which lacked lat/long data in the first place, which sometimes happens).

GeogUtils also contains open access libraries for processing shapefile/dbf files -- these are standard GIS file formats, and various publicly-accessible shapefiles might serve as sources for polygons.

Warning: the point-in-polygon operation will fail dramatically if your polygon crosses the International Dateline. The best solution in this case is to split any polygons crossing the dateline into two polygons, one on each side of the line.

===General notes===

GBIF search results often contain non-ASCII characters (e.g. international placenames) and other confusing items, e.g., web links in angle brackets, which can be misinterpreted as unmatched XML tags if a GBIF search result is read to ASCII and then an attempt is made to parse it.

In general, the Geography module will handle things fine if the results are being processed in the background; but to print results to screen, a series of functions from GeneralUtils are used to convert a string to plain ASCII. This avoids crashes e.g. when printing data to screen. Therefore, these printed-to-screen results may slightly alter the content of the original search results.

BioGeography

2009-08-19T08:47:23Z

Matzke: major update

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Summary of functions==

Each class/function has been commented with docstrings. For latest commit, see: [http://github.com/nmatzke/biopython/commits/Geography http://github.com/nmatzke/biopython/commits/Geography].

==Tutorial==

Bio.Geography is a module for gathering and processing biogeographical data. The major motivation for the module is to assist analyses of evolutionary biogeography. A variety of inference algorithms are available for such analyses, such as [http://www.ebc.uu.se/systzoo/research/diva/manual/dmanual.html DIVA] and [http://code.google.com/p/lagrange/ lagrange]. The inputs to such programs are typically (a) a phylogeny and (b) the areas inhabited by the species at the tips of the phylogeny. A researcher who has gathered data on a particular group will likely have direct access to species location data, but many large-scale analyses may require gathering large amounts of occurrence data. Automated gathering/processing of occurrence data has a variety of other applications as well, including species mapping, niche modeling, error-checking of museum records, and monitoring range changes.

Occurrence data is derived mainly from museum collections. The major source of such data is the [http://www.gbif.org/ Global Biodiversity Information Facility] (GBIF). GBIF serves occurrence data recorded by hundreds of museums worldwide. GBIF occurrence data can be [http://data.gbif.org/occurrences/ searched manually], and results downloaded (see examples on GBIF website) in various formats: spreadsheet, Google Earth KML, or the XML DarwinCore format.

GBIF can also be accessed via an API. Bio.Geography can process manually downloaded DarwinCore results, or access GBIF directly.

===Parsing a local (manually downloaded) GBIF DarwinCore XML file===

For one-off uses of GBIF, you may find it easiest to just download occurrence data in spreadsheet format (for analysis) or KML (for mapping). But for analyses of many groups, or for repeatedly updating an analysis as new data is added to GBIF, automation is desirable.

A manual search conducted on the GBIF website can return results in the form of an XML file adhering to the [http://en.wikipedia.org/wiki/Darwin_Core DarwinCore] data standard. An example file can be found in biopython's Tests/Geography directory, with the name ''utric_search_v2.xml''. This file contains over 1000 occurrence records for ''Utricularia'', a genus of carnivorous plant.

Save the utric_search_v2.xml file in your working directory (or download a similar file from GBIF). Here are suggested steps to parse the file with Bio.Geography's GbifXml module:

<pre>
from Bio.Geography.GbifXml import GbifXmlTree, GbifSearchResults

from Bio.Geography.GeneralUtils import fix_ASCII_file

xml_fn = 'utric_search_v2.xml'
</pre>

First, in order to display results to screen in python, we need to convert the file to plain ASCII (GBIF results contain all many of unusual characters from different languages, and no standardization of slanted quotes and the like; this can cause crashes when attempting to print to screen in python).

<pre>
xml_fn_new = fix_ASCII_file(xml_fn)
</pre>

This creates a new file with the string "_fixed.xml" added to the filename.

Next, we will parse the XML file into an ElementTree (a python object which contains the data from the XML file as a nested series of lists and dictionaries).

<pre>
from xml.etree import ElementTree as ET
xmltree = ET.parse(xml_fn_new)
</pre>

We can then store the element tree as nn object of Class GbifXmlTree:

<pre>gbif_recs_xmltree = GbifXmlTree(xmltree)
</pre>

Then, with the xmltree stored, we parse it into individual records (stored in individual objects of class GbifObservationRecord), which are then stored as a group in an object of class GbifSearchResults.

<pre>recs = GbifSearchResults(gbif_recs_xmltree)
recs.extract_occurrences_from_gbif_xmltree(recs.gbif_recs_xmltree)
</pre>

The list of individual observation records can be accessed at recs.obs_recs_list:

<pre>recs.obs_recs_list[0:4]
</pre>

To get the data for the first individual record:

<pre>rec = recs.obs_recs_list[0]

dir(rec)
</pre>

rec.lat will return the latitude, rec.long the longitude, etc. Certain data attributes are not found in all GBIF records; if they are missing, the field in question will contain "None".

To print all of the records in a tab-delimited table format:

<pre>
recs.print_records()
</pre>

===Checking how many matching records are hosted by GBIF===

Before we go through the trouble of downloading thousands of records, we may wish to know how many there are in GBIF first. The user must set up a dictionary containing the fields and search terms as keys and items, respectively. I.e.,

<pre>from GbifXml import GbifXmlTree, GbifSearchResults
params = {'format': 'darwin', 'scientificname': 'Genlisea*'}</pre>

"'format': 'darwin'" specifies that GBIF should return the results in DarwinCore format.

'scientificname' specifies the genus name to search on. Adding an '*' after the name will return anything that begins with "Genlisea".

The full list of search terms can be found on GBIF's [http://data.gbif.org/tutorial/services Occurrence record data service], which is linked from the [http://data.gbif.org/tutorial/services Using data from the GBIF portal].

Once you have specified your search parameters, initiate a new GbifSearchResults object and run get_numhits to get the number of hits:

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
recs = GbifSearchResults()
numhits = recs.get_numhits(params)</pre>

As of August 2009, 169 matching records existed in GBIF matching "Genlisea*"

For constrast, run the same search ''without'' the asterisk ('*'):

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea'}
numhits = recs.get_numhits(params)</pre>

We only get ~10 results -- presumably records of specimens only identified down to genus and no further.

===Downloading an individual record===

Individual records can be downloaded by key. To download an individual record:

<pre>
rec = recs.obs_recs_list[0]
key = rec.gbifkey
# (or manually)
# key = 175067484
xmlrec = recs.get_record(key)
print xmlrec</pre>

If you want to print the xmlrec ElementTree object, store xmlrec in a GbifXmlTree object and run print_xmltree:

<pre>GbifXmlTree(xmlrec).print_xmltree()</pre>

===Summary statistics for phylogenetic trees with TreeSum===

Biogeographical regions are often characterized by alpha and beta-diversity statistics: basically, these are indices of the number of species found within or between regions. Given a phylogeny for organisms in a region, phylogenetic alpha- and beta-diversity statistics can be calculated. This has been implemented in a thorough way in the [http://www.phylodiversity.net/phylocom/ phylocom package] by Webb et al., but for some purposes it is useful to calculate the statistics directly in python.

Here, we need to start with a Newick tree string:

<pre>trstr2 = "(((t9:0.385832, (t8:0.445135,t4:0.41401)C:0.024032)B:0.041436, t6:0.392496)A:0.0291131, t2:0.497673, ((t0:0.301171, t7:0.482152)E:0.0268148, ((t5:0.0984167,t3:0.488578)G:0.0349662, t1:0.130208)F:0.0318288)D:0.0273876);"

to2 = Tree(trstr2)</pre>

Then, we create a tree summary object:

<pre>ts = TreeSum(to2)</pre>

The function test_Tree will run the metrics (MPD = Mean Phylogenetic Distance, NRI = Net Relatedness Index, MNPD = Mean Nearest Neighbor Phylogenetic Distance, NTI = Nearest Taxon Index, PD = total Phylogenetic distance) and output to screen:

<pre>ts.test_Tree()</pre>

By subsetting a tree to taxa only existing within a region, statistics can be calculated by region.

===Downloading and processing large numbers of records===

GBIF only allows a maximum of 1000 observation records to be downloaded at a time (10,000 for KML records). To get more, we need to download and process them in stages.

Again we will set up our parameters dictionary, and also an "inc" variable to specify the number of records to download per server request.

<pre>params = {'format': 'darwin', 'scientificname': 'Genlisea*'}
inc = 100
recs3 = GbifSearchResults()
gbif_xmltree_list = recs3.get_all_records_by_increment(params, inc)
</pre>

As with biopython's interactions with NCBI servers, the GbifSearchResults module keeps track of when the last GBIF request was made, and requires a 3-second wait before a new request.

Each server request returns an XML string; these are parsed into GbifXmlTree objects, and a list of the returned GbifXmlTree objects is returned to gbif_xmltree_list. The individual records have also been parsed:

<pre>
recs3.print_records()
</pre>

===Classifying records into geographical regions===

Biogeographical analyses will often require that you determine what area(s) a taxon lives in. Areas are not always obviously delineated, and analysts may wish to try several different possible sets of areas and see how this influences their analysis.

Below, we set up a polygon containing the latitude/longitude coordinates for the Northern Hemisphere, and then set the "area" attribute for each matching record to "NorthernHemisphere":

<pre>
ul = (-180, 90)
ur = (180, 90)
ll = (-180, 0)
lr = (180, 0)
poly = [ul, ur, ll, lr]
polyname = "NorthernHemisphere"

recs3.print_records()
</pre>

This process can be repeated for all polygons of interest until all GBIF records have been classified (except for GBIF records which lacked lat/long data in the first place, which sometimes happens).

GeogUtils also contains open access libraries for processing shapefile/dbf files -- these are standard GIS file formats, and various publicly-accessible shapefiles might serve as sources for polygons.

Warning: the point-in-polygon operation will fail dramatically if your polygon crosses the International Dateline. The best solution in this case is to split any polygons crossing the dateline into two polygons, one on each side of the line.

===General notes===

GBIF search results often contain non-ASCII characters (e.g. international placenames) and other confusing items, e.g., web links in angle brackets, which can be misinterpreted as unmatched XML tags if a GBIF search result is read to ASCII and then an attempt is made to parse it.

In general, the Geography module will handle things fine if the results are being processed in the background; but to print results to screen, a series of functions from GeneralUtils are used to convert a string to plain ASCII. This avoids crashes e.g. when printing data to screen. Therefore, these printed-to-screen results may slightly alter the content of the original search results.

BioGeography

2009-08-19T08:06:44Z

Matzke: Added link to github commits.

BioGeography

2009-08-17T19:50:46Z

Matzke: /* Tutorial */

BioGeography

2009-08-17T19:49:36Z

Matzke: /* Parsing a local (manually downloaded) GBIF DarwinCore XML file */

BioGeography

2009-08-17T19:48:07Z

Matzke: /* Parsing a local (manually downloaded) GBIF DarwinCore XML file */

BioGeography

2009-08-17T19:47:02Z

Matzke: /* Tutorial */

BioGeography

2009-08-17T19:38:46Z

Matzke: added simple Tutorial

BioGeography

2009-07-02T18:56:01Z

Matzke: xmltree tools code

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===

Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

Updated functions have been pushed to Github [http://github.com/nmatzke/biopython/commit/5df9025ea5cd3458915db982c69422345e1da8d7 here]

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick(newickstr)====
Read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.

====list_leaves(phylo_obj)====
Print out all of the leaves in above a node object

====treelength(node)====
Gets the total branchlength above a given node by recursively adding through tree.

====phylodistance(node1, node2)====
Get the phylogenetic distance (branch length) between two nodes.

====get_distance_matrix(phylo_obj)====
Get a matrix of all of the pairwise distances between the tips of a tree.

====get_mrca_array(phylo_obj)====
Get a square list of lists (array) listing the mrca of each pair of leaves (half-diagonal matrix)

====subset_tree(phylo_obj, list_to_keep)====
Given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree.

====prune_single_desc_nodes(node)====
Follow a tree from the bottom up, pruning any nodes with only one descendant
====find_new_root(node)====
Search up tree from root and make new root at first divergence

====make_None_list_array(xdim, ydim)====
Make a list of lists ("array") with the specified dimensions

====get_PD_to_mrca(node, mrca, PD)====
Add up the phylogenetic distance from a node to the specified ancestor (mrca). Find mrca with find_1st_match.

====find_1st_match(list1, list2)====
Find the first match in two ordered lists.

====get_ancestors_list(node, anc_list)====
Get the list of ancestors of a given node

====addup_PD(node, PD)====
Adds the branchlength of the current node to the total PD measure.

====print_tree_outline_format(phylo_obj)====
Prints the tree out in "outline" format (daughter clades are indented, etc.)

====print_Node(node, rank)====
Prints the node in question, and recursively all daughter nodes, maintaining rank as it goes.

====lagrange_disclaimer()====
Just prints lagrange citation etc. in code using lagrange libraries.

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

Priority for this week:

Following up on suggestions to make the code more standard, with the priority of figuring out how I can revise the current BioPython phylogeny class, to resemble the better version in lagrange, so that there is a generic flexible phylogeny/newick parser that can be used generally as well as by my BioGeography package specifically.

Added a bunch of tools for managing/parsing xmltree structures from ElementTree parsing of XML:

====find_to_elements_w_ancs(xmltree, el_tag, anc_el_tag)====
Burrow into XML to get an element with tag el_tag, return only those el_tags underneath a particular parent element parent_el_tag

====create_sub_xmltree(element)====
Create a subset xmltree (to avoid going back to irrelevant parents)

====xml_recursive_search_w_anc(xmltree, element, el_tag, anc_el_tag, match_el_list)====
Recursively burrows down to find whatever elements with el_tag exist inside a parent_el_tag.

====xml_burrow_up(xmltree, element, anc_el_tag, found_anc)====
Burrow up xml to find anc_el_tag

====xml_burrow_up_cousin(xmltree, element, cousin_el_tag, found_cousin)====
Burrow up from element of interest, until a cousin is found with cousin_el_tag

====return_parent_in_xmltree(xmltree, child_to_search_for)====
Search through an xmltree to get the parent of child_to_search_for

====return_parent_in_element(potential_parent, child_to_search_for, returned_parent)====
Search through an XML element to return parent of child_to_search_for

====find_1st_matching_element(element, el_tag, return_element)====
Burrow down into the XML tree, retrieve the first element with the matching tag

====element_items_to_string(items)====
Input a list of items, get string back

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here]...no example script yet.

These still need to be integrated:

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-07-02T18:54:14Z

Matzke: june wk4 update

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===

Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

Updated functions have been pushed to Github [http://github.com/nmatzke/biopython/commit/5df9025ea5cd3458915db982c69422345e1da8d7 here]

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick(newickstr)====
Read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.

====list_leaves(phylo_obj)====
Print out all of the leaves in above a node object

====treelength(node)====
Gets the total branchlength above a given node by recursively adding through tree.

====phylodistance(node1, node2)====
Get the phylogenetic distance (branch length) between two nodes.

====get_distance_matrix(phylo_obj)====
Get a matrix of all of the pairwise distances between the tips of a tree.

====get_mrca_array(phylo_obj)====
Get a square list of lists (array) listing the mrca of each pair of leaves (half-diagonal matrix)

====subset_tree(phylo_obj, list_to_keep)====
Given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree.

====prune_single_desc_nodes(node)====
Follow a tree from the bottom up, pruning any nodes with only one descendant
====find_new_root(node)====
Search up tree from root and make new root at first divergence

====make_None_list_array(xdim, ydim)====
Make a list of lists ("array") with the specified dimensions

====get_PD_to_mrca(node, mrca, PD)====
Add up the phylogenetic distance from a node to the specified ancestor (mrca). Find mrca with find_1st_match.

====find_1st_match(list1, list2)====
Find the first match in two ordered lists.

====get_ancestors_list(node, anc_list)====
Get the list of ancestors of a given node

====addup_PD(node, PD)====
Adds the branchlength of the current node to the total PD measure.

====print_tree_outline_format(phylo_obj)====
Prints the tree out in "outline" format (daughter clades are indented, etc.)

====print_Node(node, rank)====
Prints the node in question, and recursively all daughter nodes, maintaining rank as it goes.

====lagrange_disclaimer()====
Just prints lagrange citation etc. in code using lagrange libraries.

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

Priority for this week:

Following up on suggestions to make the code more standard, with the priority of figuring out how I can revise the current BioPython phylogeny class, to resemble the better version in lagrange, so that there is a generic flexible phylogeny/newick parser that can be used generally as well as by my BioGeography package specifically.

Added a bunch of tools for managing/parsing xmltree structures from ElementTree parsing of XML:

====find_to_elements_w_ancs(xmltree, el_tag, anc_el_tag)====
Burrow into XML to get an element with tag el_tag, return only those el_tags underneath a particular parent element parent_el_tag

====create_sub_xmltree(element)====
Create a subset xmltree (to avoid going back to irrelevant parents)

====xml_recursive_search_w_anc(xmltree, element, el_tag, anc_el_tag, match_el_list)====
Recursively burrows down to find whatever elements with el_tag exist inside a parent_el_tag.

====xml_burrow_up(xmltree, element, anc_el_tag, found_anc)====
Burrow up xml to find anc_el_tag

====xml_burrow_up_cousin(xmltree, element, cousin_el_tag, found_cousin)====
Burrow up from element of interest, until a cousin is found with cousin_el_tag

====return_parent_in_xmltree(xmltree, child_to_search_for)====
Search through an xmltree to get the parent of child_to_search_for

====return_parent_in_element(potential_parent, child_to_search_for, returned_parent)====
Search through an XML element to return parent of child_to_search_for

====find_1st_matching_element(element, el_tag, return_element)====
Burrow down into the XML tree, retrieve the first element with the matching tag

====element_items_to_string(items)====
Input a list of items, get string back

These still need to be integrated:

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-06-24T04:47:46Z

Matzke: /* June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information. */

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===

Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

Updated functions have been pushed to Github [http://github.com/nmatzke/biopython/commit/5df9025ea5cd3458915db982c69422345e1da8d7 here]

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick(newickstr)====
Read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.

====list_leaves(phylo_obj)====
Print out all of the leaves in above a node object

====treelength(node)====
Gets the total branchlength above a given node by recursively adding through tree.

====phylodistance(node1, node2)====
Get the phylogenetic distance (branch length) between two nodes.

====get_distance_matrix(phylo_obj)====
Get a matrix of all of the pairwise distances between the tips of a tree.

====get_mrca_array(phylo_obj)====
Get a square list of lists (array) listing the mrca of each pair of leaves (half-diagonal matrix)

====subset_tree(phylo_obj, list_to_keep)====
Given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree.

====prune_single_desc_nodes(node)====
Follow a tree from the bottom up, pruning any nodes with only one descendant
====find_new_root(node)====
Search up tree from root and make new root at first divergence

====make_None_list_array(xdim, ydim)====
Make a list of lists ("array") with the specified dimensions

====get_PD_to_mrca(node, mrca, PD)====
Add up the phylogenetic distance from a node to the specified ancestor (mrca). Find mrca with find_1st_match.

====find_1st_match(list1, list2)====
Find the first match in two ordered lists.

====get_ancestors_list(node, anc_list)====
Get the list of ancestors of a given node

====addup_PD(node, PD)====
Adds the branchlength of the current node to the total PD measure.

====print_tree_outline_format(phylo_obj)====
Prints the tree out in "outline" format (daughter clades are indented, etc.)

====print_Node(node, rank)====
Prints the node in question, and recursively all daughter nodes, maintaining rank as it goes.

====lagrange_disclaimer()====
Just prints lagrange citation etc. in code using lagrange libraries.

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

Priority for this week:

Following up on suggestions to make the code more standard, with the priority of figuring out how I can revise the current BioPython phylogeny class, to resemble the better version in lagrange, so that there is a generic flexible phylogeny/newick parser that can be used generally as well as by my BioGeography package specifically.

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-06-24T04:37:19Z

Matzke: update week4 plan

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===

Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

Updated functions have been pushed to Github [http://github.com/nmatzke/biopython/commit/5df9025ea5cd3458915db982c69422345e1da8d7 here]

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick(newickstr)====
Read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.

====list_leaves(phylo_obj)====
Print out all of the leaves in above a node object

====treelength(node)====
Gets the total branchlength above a given node by recursively adding through tree.

====phylodistance(node1, node2)====
Get the phylogenetic distance (branch length) between two nodes.

====get_distance_matrix(phylo_obj)====
Get a matrix of all of the pairwise distances between the tips of a tree.

====get_mrca_array(phylo_obj)====
Get a square list of lists (array) listing the mrca of each pair of leaves (half-diagonal matrix)

====subset_tree(phylo_obj, list_to_keep)====
Given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree.

====prune_single_desc_nodes(node)====
Follow a tree from the bottom up, pruning any nodes with only one descendant
====find_new_root(node)====
Search up tree from root and make new root at first divergence

====make_None_list_array(xdim, ydim)====
Make a list of lists ("array") with the specified dimensions

====get_PD_to_mrca(node, mrca, PD)====
Add up the phylogenetic distance from a node to the specified ancestor (mrca). Find mrca with find_1st_match.

====find_1st_match(list1, list2)====
Find the first match in two ordered lists.

====get_ancestors_list(node, anc_list)====
Get the list of ancestors of a given node

====addup_PD(node, PD)====
Adds the branchlength of the current node to the total PD measure.

====print_tree_outline_format(phylo_obj)====
Prints the tree out in "outline" format (daughter clades are indented, etc.)

====print_Node(node, rank)====
Prints the node in question, and recursively all daughter nodes, maintaining rank as it goes.

====lagrange_disclaimer()====
Just prints lagrange citation etc. in code using lagrange libraries.

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

Priority for this week:

Following up on suggestions to make the code more standard, with the priority of figuring out how I can revise the current BioPython phylogeny class, to resemble the better version in lagrange, so that there is a generic flexible phylogeny/newick parser that can be used generally as well as by my BioGeography package specifically.

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-06-24T04:35:36Z

Matzke: /* June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information. */

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===

Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

Updated functions have been pushed to Github [http://github.com/nmatzke/biopython/commit/5df9025ea5cd3458915db982c69422345e1da8d7 here]

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick(newickstr)====
Read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.

====list_leaves(phylo_obj)====
Print out all of the leaves in above a node object

====treelength(node)====
Gets the total branchlength above a given node by recursively adding through tree.

====phylodistance(node1, node2)====
Get the phylogenetic distance (branch length) between two nodes.

====get_distance_matrix(phylo_obj)====
Get a matrix of all of the pairwise distances between the tips of a tree.

====get_mrca_array(phylo_obj)====
Get a square list of lists (array) listing the mrca of each pair of leaves (half-diagonal matrix)

====subset_tree(phylo_obj, list_to_keep)====
Given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree.

====prune_single_desc_nodes(node)====
Follow a tree from the bottom up, pruning any nodes with only one descendant
====find_new_root(node)====
Search up tree from root and make new root at first divergence

====make_None_list_array(xdim, ydim)====
Make a list of lists ("array") with the specified dimensions

====get_PD_to_mrca(node, mrca, PD)====
Add up the phylogenetic distance from a node to the specified ancestor (mrca). Find mrca with find_1st_match.

====find_1st_match(list1, list2)====
Find the first match in two ordered lists.

====get_ancestors_list(node, anc_list)====
Get the list of ancestors of a given node

====addup_PD(node, PD)====
Adds the branchlength of the current node to the total PD measure.

====print_tree_outline_format(phylo_obj)====
Prints the tree out in "outline" format (daughter clades are indented, etc.)

====print_Node(node, rank)====
Prints the node in question, and recursively all daughter nodes, maintaining rank as it goes.

====lagrange_disclaimer()====
Just prints lagrange citation etc. in code using lagrange libraries.

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-06-24T04:35:06Z

Matzke: updated week 3 results

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===

Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

Updated functions have been pushed to Github [http://github.com/nmatzke/biopython/commit/5df9025ea5cd3458915db982c69422345e1da8d7 here]

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick(newickstr)====
Read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.

====list_leaves(phylo_obj)====
Print out all of the leaves in above a node object

====treelength(node)====
Gets the total branchlength above a given node by recursively adding through tree.

====phylodistance(node1, node2)====
Get the phylogenetic distance (branch length) between two nodes.

====get_distance_matrix(phylo_obj)====
Get a matrix of all of the pairwise distances between the tips of a tree.

====get_mrca_array(phylo_obj)====
Get a square list of lists (array) listing the mrca of each pair of leaves (half-diagonal matrix)

====subset_tree(phylo_obj, list_to_keep)====
Given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree.

====prune_single_desc_nodes(node)====
Follow a tree from the bottom up, pruning any nodes with only one descendent

find_new_root(node)====
Search up tree from root and make new root at first divergence

====make_None_list_array(xdim, ydim)====
Make a list of lists ("array") with the specified dimensions

====get_PD_to_mrca(node, mrca, PD)====
Add up the phylogenetic distance from a node to the specified ancestor (mrca). Find mrca with find_1st_match.

====find_1st_match(list1, list2)====
Find the first match in two ordered lists.

====get_ancestors_list(node, anc_list)====
Get the list of ancestors of a given node

====addup_PD(node, PD)====
Adds the branchlength of the current node to the total PD measure.

print_tree_outline_format(phylo_obj)====
Prints the tree out in "outline" format (daughter clades are indented, etc.)

====print_Node(node, rank)====
Prints the node in question, and recursively all daughter nodes, maintaining rank as it goes.

====lagrange_disclaimer()====
Just prints lagrange citation etc. in code using lagrange libraries.

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-06-15T00:48:02Z

Matzke: week 3 update: Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===

Added functions download & parse large numbers of records, get TaxonOccurrence gbifKeys, and search with those keys.

====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

Updated functions have been pushed to Github [http://github.com/nmatzke/biopython/commit/5df9025ea5cd3458915db982c69422345e1da8d7 here]

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick====
read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.
====treelength====
get the total branchlength above a given node
====phylodistance====
get the phylogenetic distance (branch length) between two nodes
====get_distance_matrix====
get a matrix of all of the pairwise distances between the tips of a tree.

This can be a slow function for large trees; currently I call a java function from python, this is probably the way to go.

====subset_tree====
given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree (as in Phylomatic)

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-06-14T23:58:48Z

Matzke: uploaded June week 2 functions

==Introduction==

BioGeography is a module under development by [[User:Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The source code is in the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development of the module [http://biopython.org/wiki/BioGeography here]. The new module is being documented on [http://www.biopython.org/wiki/Main_Page the BioPython wiki] as [http://biopython.org/wiki/BioGeography BioGeography].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

Note: all major functions are being placed in the file geogUtils.py for the moment. Also, the immediate goal is to just get everything basically working, so details of where to put various functions, what to call them, etc. are being left for later.

Code usage: For a few things, an entire necessary function already exists (e.g. for reading a shapefile), and re-inventing the wheel seems pointless. In most cases the material used appears to be open source (e.g. previous Google Summer of Code). For a few short code snippets found online in various places I am less sure. In all cases I am noting the source and when finalizing this project I will go back and determine if the stuff is considered copyright, and if so email the authors for permission to use.

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
====readshpfile====
Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
====extract_latlong====
Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
====shapefile_points_in_poly, tablefile_points_in_poly====
Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

====Code====
* [http://github.com/nmatzke/biopython/commit/4d963a65ce48b9d50327f191dedcc76abbb149be Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data.

====access_gbif====
utility function invoked by other functions, user inputs parameters and the GBIF response in XML/DarwinCore format is returned. The relevant GBIF web service, and the search commands etc., are here: http://data.gbif.org/ws/rest/occurrence
====get_hits====
Get the actual hits that are be returned by a given search, returns filename were they are saved
====get_xml_hits====
Like get_hits, but returns a parsed XML tree
====fix_ASCII====
files downloaded from GBIF contain HTML character entities & unicode characters (e.g. umlauts mostly) which mess up printing results to prompt in Python, this fixes that
====paramsdict_to_string====
converts user's search parameters (in python dictionary format; see here for params http://data.gbif.org/ws/rest/occurrence ) to a string for submission via access_gbif
====xmlstring_to_xmltree(xmlstring)====
Take the text string returned by GBIF and parse to an XML tree using ElementTree. Requires the intermediate step of saving to a temporary file (required to make ElementTree.parse work, apparently).
====element_items_to_dictionary====
If the XML tree element has items encoded in the tag, e.g. key/value or whatever, this function puts them in a python dictionary and returns them.
====extract_numhits====
Search an element of a parsed XML string and find the number of hits, if it exists. Recursively searches, if there are subelements.
====print_xmltree====
Prints all the elements & subelements of the xmltree to screen (may require fix_ASCII to input file to succeed)
====Deleted (turns out this was unnecessary): gettaxonconceptkey====
user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

====Code====
* [http://github.com/nmatzke/biopython/commits/Geography Code fulfilling these tasks is uploaded here], along with an example script and data files to run.

===June, week 2: Functions to get GBIF records===
====get_record====
Retrieves a single specified record in DarwinCore XML format, and returns an xmltree for it.

====extract_occurrence_elements====
Returns a list of the elements, picking elements by TaxonOccurrence; this should return a list of elements equal to the number of hits.

====extract_taxonconceptkeys_tolist====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns list.

====extract_taxonconceptkeys_tofile====
Searches an element in an XML tree for TaxonOccurrence gbifKeys, and the complete name. Searches recursively, if there are subelements. Returns file at outfh.

====get_all_records_by_increment====
Download all of the records in stages, store in list of elements. Increments of e.g. 100 to not overload server. Currently stores results in a list of tempfiles which is returned (could return a list of handles I guess).

====Code====

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====read_ultrametric_Newick====
read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.
====treelength====
get the total branchlength above a given node
====phylodistance====
get the phylogenetic distance (branch length) between two nodes
====get_distance_matrix====
get a matrix of all of the pairwise distances between the tips of a tree.

This can be a slow function for large trees; currently I call a java function from python, this is probably the way to go.

====subset_tree====
given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree (as in Phylomatic)

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

====alphadiversity====
alpha diversity of a region (number of taxa in the region)
====betadiversity====
beta diversity (Sorenson’s index) between two regions
====alphaphylodistance====
total branchlength of a phylogeny of taxa within a region
====phylosor====
phylogenetic Sorenson’s index between two regions
====meanphylodistance====
average distance between all tips on a region’s phylogeny
====meanminphylodistance====
average distance to nearest neighbor for tips on a region’s phylogeny
====netrelatednessindex====
standardized index of mean phylodistance
====nearesttaxonindex====
standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

====make_lagrange_species_range_inputs====
convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
====check_input_lagrange_tree====
checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
====parse_lagrange_output====
take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
====get_polygon_skeleton====
this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
====assign_node_locations_in_region====
within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
====assign_node_locations_between_regions====
connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
====write_history_to_shapefile====
write the biogeographic history to a shapefile
====write_history_to_KML====
write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-06-14T23:48:20Z

Matzke: get_record info

BioGeography

2009-06-14T21:07:55Z

Matzke: /* print_xmltree */

BioGeography

2009-06-14T19:18:12Z

Matzke: /* June, week 1: Functions to search GBIF and download occurrence records */

BioGeography

2009-06-14T19:15:25Z

Matzke:

BioGeography

2009-06-14T19:02:32Z

Matzke: changed formatting to make functions into subheadings

BioGeography

2009-06-14T19:00:35Z

Matzke: updated function names to refer to functions in geogUtils.py

BioGeography

2009-06-14T18:23:45Z

Matzke: notes on geogUtils

BioGeography

2009-06-14T18:17:16Z

Matzke: updated function names to refer to functions in geogUtils.py

BioGeography

2009-06-02T14:06:08Z

Matzke: update on week1

BioGeography

2009-05-22T21:57:03Z

Matzke: fix github references etc

Active projects

2009-05-22T21:51:04Z

Matzke: /* Biogeography (GSoC) */

This page provides a central location to collect references to active projects. This is a good place to start if you are interested in contributing to Biopython and want to find larger projects in progress. For developers, use this to reference git branches or other projects which you will be working on for an extended period of time. Please keep it up to date as projects are finished and integrated into Biopython.

== Current projects ==

=== Population Genetics development ===

Giovanni and Tiago are working on expanding population genetics code in Biopython. See the [[PopGen_dev|PopGen development page]] for more details.

=== GFF parser ===

Brad is working on a Biopython GFF parser. Source code is available from [http://github.com/chapmanb/bcbb/tree/master/gff git hub]. See blog posts on the [http://bcbio.wordpress.com/2009/03/08/initial-gff-parser-for-biopython/ initial implementation] and [http://bcbio.wordpress.com/2009/03/22/mapreduce-implementation-of-gff-parsing-for-biopython/ MapReduce parallel version].

=== PhyloXML driver (GSoC) ===

Eric is working on supporting the [http://www.phyloxml.org/ PhyloXML] format, as a [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798969 project] for Google Summer of Code 2009. Brad is mentoring this project. The code lives on a branch in [http://github.com/etal/biopython/tree/phyloxml GitHub], and you can see a timeline and other info about ongoing development [http://github.com/etal/biopython/tree/phyloxml/Bio/PhyloXML/ here]. The new module is being documented on this wiki as [[PhyloXML]].

=== Biogeography (GSoC) ===

[[Matzke|Nick]] is working on developing a Biogeography module for BioPython. This work is funded by [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The code currently lives at the Bio/Geography directory of the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development [[BioGeography|here]]. The new module is being documented on this wiki as [[BioGeography]].

=== Roche 454 SFF parsing in Bio.SeqIO ===

See [http://bugzilla.open-bio.org/show_bug.cgi?id=2837 Bug 2837], based on code from Jose Blanca.

=== Open Enhancement Bugs ===

This [http://bugzilla.open-bio.org/buglist.cgi?product=Biopython&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_severity=enhancement Bugzilla Search] will list all open enhancement bugs (any filed by core developers are fairly likely to be integrated, some are just wish list entries).

== Project ideas ==

Please add any ideas or proposals for new additions to Biopython. Bugs and enhancements for current code should be discussed though our bugzilla interface.

* Use SQLAlchemy, an object relational mapper, for BioSQL internals. This would add an additional external dependency to Biopython, but provides ready support for additional databases like SQLite. It also would provide a raw object interface to BioSQL databases when the SeqRecord-like interface is not sufficient. Brad has some initial code for this.

* Revamp the GEO SOFT parser, drawing on the ideas used in [http://www.bioconductor.org/packages/bioc/html/GEOquery.html Sean Davis' GEOquery parser in R/Bioconductor]. See also [http://www.warwick.ac.uk/go/peter_cock/r/geo/ this page].

== Enhancement list ==

Maintaining software involves incremental improvements for new format changes and removal of bugs. Please see our [http://bugzilla.open-bio.org/ bugzilla] page for a current list. Post to the developer mailing list if you are interested in tackling any open issues.

Active projects

2009-05-22T21:50:26Z

Matzke: /* Biogeography (GSoC) */

This page provides a central location to collect references to active projects. This is a good place to start if you are interested in contributing to Biopython and want to find larger projects in progress. For developers, use this to reference git branches or other projects which you will be working on for an extended period of time. Please keep it up to date as projects are finished and integrated into Biopython.

== Current projects ==

=== Population Genetics development ===

Giovanni and Tiago are working on expanding population genetics code in Biopython. See the [[PopGen_dev|PopGen development page]] for more details.

=== GFF parser ===

Brad is working on a Biopython GFF parser. Source code is available from [http://github.com/chapmanb/bcbb/tree/master/gff git hub]. See blog posts on the [http://bcbio.wordpress.com/2009/03/08/initial-gff-parser-for-biopython/ initial implementation] and [http://bcbio.wordpress.com/2009/03/22/mapreduce-implementation-of-gff-parsing-for-biopython/ MapReduce parallel version].

=== PhyloXML driver (GSoC) ===

Eric is working on supporting the [http://www.phyloxml.org/ PhyloXML] format, as a [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798969 project] for Google Summer of Code 2009. Brad is mentoring this project. The code lives on a branch in [http://github.com/etal/biopython/tree/phyloxml GitHub], and you can see a timeline and other info about ongoing development [http://github.com/etal/biopython/tree/phyloxml/Bio/PhyloXML/ here]. The new module is being documented on this wiki as [[PhyloXML]].

=== Biogeography (GSoC) ===

[[Matzke|Nick]] is working on developing a Biogeography module for BioPython. This work is funded by [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The code currently lives at the [http://github.com/nmatzke/biopython/tree/Geography Geography fork of the nmatzke branch on GitHub], and you can see a timeline and other info about ongoing development [[BioGeography|here]]. The new module is being documented on this wiki as [[BioGeography]].

=== Roche 454 SFF parsing in Bio.SeqIO ===

See [http://bugzilla.open-bio.org/show_bug.cgi?id=2837 Bug 2837], based on code from Jose Blanca.

=== Open Enhancement Bugs ===

This [http://bugzilla.open-bio.org/buglist.cgi?product=Biopython&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_severity=enhancement Bugzilla Search] will list all open enhancement bugs (any filed by core developers are fairly likely to be integrated, some are just wish list entries).

== Project ideas ==

Please add any ideas or proposals for new additions to Biopython. Bugs and enhancements for current code should be discussed though our bugzilla interface.

* Use SQLAlchemy, an object relational mapper, for BioSQL internals. This would add an additional external dependency to Biopython, but provides ready support for additional databases like SQLite. It also would provide a raw object interface to BioSQL databases when the SeqRecord-like interface is not sufficient. Brad has some initial code for this.

* Revamp the GEO SOFT parser, drawing on the ideas used in [http://www.bioconductor.org/packages/bioc/html/GEOquery.html Sean Davis' GEOquery parser in R/Bioconductor]. See also [http://www.warwick.ac.uk/go/peter_cock/r/geo/ this page].

== Enhancement list ==

Maintaining software involves incremental improvements for new format changes and removal of bugs. Please see our [http://bugzilla.open-bio.org/ bugzilla] page for a current list. Post to the developer mailing list if you are interested in tackling any open issues.

BioGeography

2009-05-20T05:03:14Z

Matzke: /* Introduction */

BioGeography

2009-05-20T04:58:36Z

Matzke: /* Work Plan */

==Introduction==

BioGeography is a module under development by [[Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The code currently lives at the nmatzke branch on [http://github.com/nmatzke/biopython/tree/master GitHub], and you can see a timeline and other info about ongoing development [http://github.com/nmatzke/biopython/tree/master here].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
* Function: readshapefile
::Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
* Function: readGBIFrecord
::Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
* Function: points2ranges
::Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data. The relevant GBIF web service is here: http://data.gbif.org/ws/rest/occurrence

* Function: searchGBIFrecords – user inputs parameters and a list of GBIF records is returned
* Function: gettaxonconceptkey – user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

===June, week 2: Functions to get GBIF records===
* Function: getGBIFrecord – retrieves the record (for this project, just the “brief” format of the record) and saves it
* Function: getGBIFrecords – calls getGBIFrecord for a user-specified list of records (derived from searchGBIFrecords function call)
* Function: readGBIFrecords – calls readGBIFrecord on a list of saved records

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

* Function: read_ultrametric_Newick – read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.
* Function: treelength – get the total branchlength above a given node
* Function: phylodistance – get the phylogenetic distance (branch length) between two nodes
* Function: get_distance_matrix – get a matrix of all of the pairwise distances between the tips of a tree.

This can be a slow function for large trees; currently I call a java function from python, this is probably the way to go.

* Function: subset_tree – given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree (as in Phylomatic)

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

* Function: alphadiversity – alpha diversity of a region (number of taxa in the region)
* Function: betadiversity – beta diversity (Sorenson’s index) between two regions
* Function: alphaphylodistance – total branchlength of a phylogeny of taxa within a region
* Function: phylosor – phylogenetic Sorenson’s index between two regions
* Function: meanphylodistance – average distance between all tips on a region’s phylogeny
* Function: meanminphylodistance – average distance to nearest neighbor for tips on a region’s phylogeny
* Function: netrelatednessindex – standardized index of mean phylodistance
* Function: nearesttaxonindex – standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

* Function: make_lagrange_species_range_inputs – convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
* Function: check_input_lagrange_tree – checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
* Function: parse_lagrange_output – take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
* Function: get_polygon_skeleton – this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
* Function: assign_node_locations_in_region -- within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
* Function: assign_node_locations_between_regions – connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
* Function: write_history_to_shapefile -- write the biogeographic history to a shapefile
* Function: write_history_to_KML – write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing===

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-05-20T04:57:00Z

Matzke: starter

==Introduction==

BioGeography is a module under development by [[Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The code currently lives at the nmatzke branch on [http://github.com/nmatzke/biopython/tree/master GitHub], and you can see a timeline and other info about ongoing development [http://github.com/nmatzke/biopython/tree/master here].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

==Work Plan==

===May, week 1: Functions to read locality data and place points in geographic regions (Tasks 1-2)===
* Function: readshapefile
::Parses polygon, point, and multipoint shapefiles into python objects (storing latitude/longitude coordinates and feature names, e.g. the region name associated with each polygon)
* Function: readGBIFrecord
::Parse a manually downloaded GBIF record, extracting latitude/longitude and taxon names
* Function: points2ranges
::Input geographic points, determine which region (polygon) each range falls in (via point-in-polygon algorithm); also output points that are unclassified, e.g. some GBIF locations were mis-typed in the source database, so a record will fall in the middle of the ocean.

===June, week 1: Functions to search GBIF and download occurrence records===

Note: creating functions for all possible interactions with GBIF is not possible in the time available, I will just focus on searching and downloading basic record occurrence record data. The relevant GBIF web service is here: http://data.gbif.org/ws/rest/occurrence

* Function: searchGBIFrecords – user inputs parameters and a list of GBIF records is returned
* Function: gettaxonconceptkey – user inputs a taxon name and gets the GBIF key back (useful for searching GBIF records and finding e.g. synonyms and daughter taxa). The GBIF taxon concepts are accessed via the taxon web service: http://data.gbif.org/ws/rest/taxon

===June, week 2: Functions to get GBIF records===
* Function: getGBIFrecord – retrieves the record (for this project, just the “brief” format of the record) and saves it
* Function: getGBIFrecords – calls getGBIFrecord for a user-specified list of records (derived from searchGBIFrecords function call)
* Function: readGBIFrecords – calls readGBIFrecord on a list of saved records

===June, week 3: Functions to read user-specified Newick files (with ages and internal node labels) and generate basic summary information.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

* Function: read_ultrametric_Newick – read a Newick file into a tree object (a series of node objects links to parent and daughter nodes), also reading node ages and node labels if any.
* Function: treelength – get the total branchlength above a given node
* Function: phylodistance – get the phylogenetic distance (branch length) between two nodes
* Function: get_distance_matrix – get a matrix of all of the pairwise distances between the tips of a tree.

This can be a slow function for large trees; currently I call a java function from python, this is probably the way to go.

* Function: subset_tree – given a list of tips and a tree, remove all other tips and resulting redundant nodes to produce a new smaller tree (as in Phylomatic)

===June, week 4: Functions to summarize taxon diversity in regions, given a phylogeny and a list of taxa and the regions they are in.===

(note: I have scripts doing all of these functions already, so the work is integrating them into a Biopython module, testing them, etc.)

* Function: alphadiversity – alpha diversity of a region (number of taxa in the region)
* Function: betadiversity – beta diversity (Sorenson’s index) between two regions
* Function: alphaphylodistance – total branchlength of a phylogeny of taxa within a region
* Function: phylosor – phylogenetic Sorenson’s index between two regions
* Function: meanphylodistance – average distance between all tips on a region’s phylogeny
* Function: meanminphylodistance – average distance to nearest neighbor for tips on a region’s phylogeny
* Function: netrelatednessindex – standardized index of mean phylodistance
* Function: nearesttaxonindex – standardized index of mean minimum phylodistance

===July, week 1: lagrange input/output handling (Task 6)===

(note: lagrange requires a number of input files, e.g. hypothesized histories of connectivity; the only inputs suitable for automation in this project are the species ranges and phylogeny

* Function: make_lagrange_species_range_inputs – convert list of taxa/ranges to input format: http://www.reelab.net/lagrange/configurator/index
* Function: check_input_lagrange_tree – checks if input phylogeny meets the requirements for lagrange, i.e. has ultrametric branchlengths, tips end at time 0, tip names are in the species/ranges input file
* Function: parse_lagrange_output – take the output file from lagrange and get ages and estimated regions for each node

===July, weeks 2-3: Devise algorithm for representing estimated node histories (location of nodes in categorical regions) as latitude/longitude points, necessary for input into geographic display files.===

* Regarding where to put reconstructed nodes, or tips that where the only location information is region. Within regions, dealing with linking already geo-located tips, spatial averaging can be used as currently happens with GeoPhyloBuilder. If there is only one node in a region the centroid or something similar could be used (i.e. the "root" of the polygon skeleton would deal even with weird concave polygons).
* If there are multiple ancestral nodes or region-only tips in a region, they need to be spread out inside the polygon, or lines will just be drawn on top of each other. This can be done by putting the most ancient node at the root of the polygon skeleton/medial axis, and then spreading out the daughter nodes along the skeleton/medial axis of the polygon.
* Function: get_polygon_skeleton – this is a standard operation: http://en.wikipedia.org/wiki/Straight_skeleton
* Function: assign_node_locations_in_region -- within a region’s polygon, given a list of nodes, their relationship, and ages, spread the nodes out along the middle 50% of the longest axis of the polygon skeleton, with the oldest node in the middle
* Function: assign_node_locations_between_regions – connect the nodes that are linked to branches that cross between regions (for this initial project, just the great circle lines)

===July, week 4 and August, week 1: Write functions for converting the output from the above into graphical display formats, e.g. shapefiles for ArcGIS, KML files for Google Earth.===
* Function: write_history_to_shapefile -- write the biogeographic history to a shapefile
* Function: write_history_to_KML – write the biogeographic history to a KML file for input into Google Earth

===August, week 2: Beta testing

Make the series of functions available, along with suggested input files; have others run on various platforms, with various levels of expertise (e.g. Evolutionary Biogeography Discussion Group at U.C. Berkeley). Also get final feedback from mentors and advisors.

===August, week 3: Wrapup===

Assemble documentation, FAQ, project results writeup for Phyloinformatics Summer of Code.

BioGeography

2009-05-20T04:50:20Z

Matzke: starter

BioGeography is a module under development by [[Matzke|Nick Matzke]] for a [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] project. It is run through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The code currently lives at the nmatzke branch on [http://github.com/nmatzke/biopython/tree/master GitHub], and you can see a timeline and other info about ongoing development [http://github.com/nmatzke/biopython/tree/master here].

'''Abstract:''' Create a BioPython module that will enable users to automatically access and parse species locality records from online biodiversity databases; link these to user-specified phylogenies; calculate basic alpha- and beta-phylodiversity summary statistics, produce input files for input into the various inference algorithms available for inferring historical biogeography; convert output from these programs into files suitable for mapping, e.g. in Google Earth (KML files).

Active projects

2009-05-20T04:46:37Z

Matzke: /* Current projects */

This page provides a central location to collect references to active projects. This is a good place to start if you are interested in contributing to Biopython and want to find larger projects in progress. For developers, use this to reference git branches or other projects which you will be working on for an extended period of time. Please keep it up to date as projects are finished and integrated into Biopython.

== Current projects ==

=== Population Genetics development ===

Giovanni and Tiago are working on expanding population genetics code in Biopython. See the [[PopGen_dev|PopGen development page]] for more details.

=== GFF parser ===

Brad is working on a Biopython GFF parser. Source code is available from [http://github.com/chapmanb/bcbb/tree/master/gff git hub]. See blog posts on the [http://bcbio.wordpress.com/2009/03/08/initial-gff-parser-for-biopython/ initial implementation] and [http://bcbio.wordpress.com/2009/03/22/mapreduce-implementation-of-gff-parsing-for-biopython/ MapReduce parallel version].

=== PhyloXML driver (GSoC) ===

Eric is working on supporting the [http://www.phyloxml.org/ PhyloXML] format, as a [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798969 project] for Google Summer of Code 2009. Brad is mentoring this project. The code lives on a branch in [http://github.com/etal/biopython/tree/phyloxml GitHub], and you can see a timeline and other info about ongoing development [http://github.com/etal/biopython/tree/phyloxml/Bio/PhyloXML/ here]. The new module is being documented on this wiki as [[PhyloXML]].

=== Biogeography (GSoC) ===

[[Matzke|Nick]] is working on developing a Biogeography module for BioPython. This work is funded by [http://socghop.appspot.com/program/home/google/gsoc2009 Google Summer of Code 2009] through NESCENT's [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Phyloinformatics Summer of Code 2009]. See the project proposal at: [http://socghop.appspot.com/student_project/show/google/gsoc2009/nescent/t124022798250 Biogeographical Phylogenetics for BioPython]. The mentors are [http://blackrim.org/ Stephen Smith] (primary), [http://bcbio.wordpress.com/ Brad Chapman], and [http://evoviz.nescent.org/ David Kidd]. The code currently lives at the nmatzke branch on [http://github.com/nmatzke/biopython/tree/master GitHub], and you can see a timeline and other info about ongoing development [http://github.com/nmatzke/biopython/tree/master here]. The new module is being documented on this wiki as [[BioGeography]].

=== Open Enhancement Bugs ===

This [http://bugzilla.open-bio.org/buglist.cgi?product=Biopython&bug_status=NEW&bug_status=ASSIGNED&bug_status=REOPENED&bug_severity=enhancement Bugzilla Search] will list all open enhancement bugs (any filed by core developers are fairly likely to be integrated, some are just wish list entries).

== Project ideas ==

Please add any ideas or proposals for new additions to Biopython. Bugs and enhancements for current code should be discussed though our bugzilla interface.

* Use SQLAlchemy, an object relational mapper, for BioSQL internals. This would add an additional external dependency to Biopython, but provides ready support for additional databases like SQLite. It also would provide a raw object interface to BioSQL databases when the SeqRecord-like interface is not sufficient. Brad has some initial code for this.

* Revamp the GEO SOFT parser, drawing on the ideas used in [http://www.bioconductor.org/packages/bioc/html/GEOquery.html Sean Davis' GEOquery parser in R/Bioconductor]. See also [http://www.warwick.ac.uk/go/peter_cock/r/geo/ this page].

* Roche 454 SFF support in Bio.SeqIO is being discussed on the mailing lists.

== Enhancement list ==

Maintaining software involves incremental improvements for new format changes and removal of bugs. Please see our [http://bugzilla.open-bio.org/ bugzilla] page for a current list. Post to the developer mailing list if you are interested in tackling any open issues.

User:Matzke

2009-05-20T03:58:39Z

Matzke:

Nick Matzke is working on the [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Google/Phyloinformatics Summer of Code 2009] project "[https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009#Biogeographical_Phylogenetics_for_BioPython Biogeographical Phylogenetics for BioPython]."

Nick is a Ph.D. candidate in the Department of Integrative Biology at University of California, Berkeley. [http://ib.berkeley.edu/people/students/person_detail.php?person=370 Departmental page] -- [http://fisher.berkeley.edu/cteg/members/matzke.html Lab page].

He has also done some other strange and interesting things. See [http://en.wikipedia.org/wiki/Nick_Matzke|wikipedia] and [http://www.google.com/search?hl=en&rlz=1B3GGGL_enUS239US239&q=evolution+matzke&btnG=Search|google].

User:Matzke

2009-05-20T03:57:56Z

Matzke: starter

Nick Matzke is working on the [https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009 Google/Phyloinformatics Summer of Code 2009] project "[https://www.nescent.org/wg_phyloinformatics/Phyloinformatics_Summer_of_Code_2009#Biogeographical_Phylogenetics_for_BioPython Biogeographical Phylogenetics for BioPython]."

Nick is a Ph.D. candidate in the Department of Integrative Biology at University of California, Berkeley. [http://ib.berkeley.edu/people/students/person_detail.php?person=370|Departmental page] -- [http://fisher.berkeley.edu/cteg/members/matzke.html|Lab page].

He has also done some other strange and interesting things. See [http://en.wikipedia.org/wiki/Nick_Matzke|wikipedia] and [http://www.google.com/search?hl=en&rlz=1B3GGGL_enUS239US239&q=evolution+matzke&btnG=Search|google].