qiime/qiime — pull request #651 by wdwvt1 (2013-01-25 21:29:40+00:00)
Title: Relatedness speedup

This is a major overhall of the relatedness.py code including the script, library, and tests. The motivation was that relatedness.py was prohibitively slow on even moderately sized trees. I refactored many of the functions to be vectorized and eliminate some redundant sorting steps. I rewrote the tests to test the new functions, and I rewrote the documentation to include both steps to test what I did against Phylocom 4.2 and to make it clearer, add more error handling.

As a demonstration of the overall speed up here is the results of timing relatedness.py using the new version and the old version:

will ~ $time relatedness.py -t /Users/will/Desktop/relatedness_test.tre -g /Users/will/Desktop/gtips.txt
nri: -0.30626326401
nti: 1.00335015542

real	0m4.408s
user	0m4.242s
sys	0m0.130s
will ~ $time relatedness.py -t /Users/will/Desktop/relatedness_test.tre -g /Users/will/Desktop/gtips.txt
nri: -0.365039519338
nti: 1.06636287862

real	0m57.850s
user	0m57.010s
sys	0m0.237s

A speed increase of about 13.2 times.

In addition, I tested the results against Phylocom 4.2 to make sure that they still agreed. Using 100 runs of relatedness vs 87 of Phylocom:

100 tests (87 for phylocom) using 1000 iters each:
nri
phylocom - mean = .4481, std = .05529
rel - mean = .4516, std = .048414

nti
phylocom - mean = -1.2081908, std = 0.03177133
rel - mean = -1.23526, std = 0.02437

The distributions are very close and I believe any differences are caused by the different randomization procedures being used.