[Biopython-dev] Added NN search

Thomas Hamelryck thamelry at vub.ac.be
Fri Jun 21 06:02:40 EDT 2002


Added a simple but effective method to the KDTree class to search 
all point pairs within a given radius (simply sort points along x and then
check all points with delta(x)<radius).

For 10^5 random 3D points (in a cube with size 1x1x1, query
radius 0.01) on a 1000 Mhz machine:

KDTree method (including building the tree): 45 s
Simple sort method: 5s 

Of course, the KDTree method could still be faster for certain point sets. I 
will test both methods on some structures to see which one is faster. 

BTW, I also like Iddo's snake! And a helical pattern on its skin would indeed
be nice...

---
Thomas Hamelryck      Vrije Universiteit Brussel (VUB)
Intitute for Molecular Biology           ULTR Department
Paardenstraat 65   1640 Sint-Gensius-Rode    Belgium
              http://ultr.vub.ac.be/~thomas



More information about the Biopython-dev mailing list