<?xml version="1.0" encoding="ascii"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> <head> <title>Bio.KDTree.KDTree</title> <link rel="stylesheet" href="epydoc.css" type="text/css" /> <script type="text/javascript" src="epydoc.js"></script> </head> <body bgcolor="white" text="black" link="blue" vlink="#204080" alink="#204080"> <!-- ==================== NAVIGATION BAR ==================== --> <table class="navbar" border="0" width="100%" cellpadding="0" bgcolor="#a0c0ff" cellspacing="0"> <tr valign="middle"> <!-- Tree link --> <th> <a href="module-tree.html">Trees</a> </th> <!-- Index link --> <th> <a href="identifier-index.html">Indices</a> </th> <!-- Help link --> <th> <a href="help.html">Help</a> </th> <th class="navbar" width="100%"></th> </tr> </table> <table width="100%" cellpadding="0" cellspacing="0"> <tr valign="top"> <td width="100%"> <span class="breadcrumbs"> <a href="Bio-module.html">Package Bio</a> :: <a href="Bio.KDTree-module.html">Package KDTree</a> :: Module KDTree </span> </td> <td> <table cellpadding="0" cellspacing="0"> <!-- hide/show private --> <tr><td align="right"><span class="options">[<a href="javascript:void(0);" class="privatelink" onclick="toggle_private();">hide private</a>]</span></td></tr> <tr><td align="right"><span class="options" >[<a href="frames.html" target="_top">frames</a >] | <a href="Bio.KDTree.KDTree-pysrc.html" target="_top">no frames</a>]</span></td></tr> </table> </td> </tr> </table> <h1 class="epydoc">Source Code for <a href="Bio.KDTree.KDTree-module.html">Module Bio.KDTree.KDTree</a></h1> <pre class="py-src"> <a name="L1"></a><tt class="py-lineno"> 1</tt> <tt class="py-line"><tt class="py-docstring">"""</tt> </tt> <a name="L2"></a><tt class="py-lineno"> 2</tt> <tt class="py-line"><tt class="py-docstring">The KD tree data structure can be used for all kinds of searches that</tt> </tt> <a name="L3"></a><tt class="py-lineno"> 3</tt> <tt class="py-line"><tt class="py-docstring">involve N-dimensional vectors, e.g. neighbor searches (find all points</tt> </tt> <a name="L4"></a><tt class="py-lineno"> 4</tt> <tt class="py-line"><tt class="py-docstring">within a radius of a given point) or finding all point pairs in a set</tt> </tt> <a name="L5"></a><tt class="py-lineno"> 5</tt> <tt class="py-line"><tt class="py-docstring">that are within a certain radius of each other. See "Computational Geometry: </tt> </tt> <a name="L6"></a><tt class="py-lineno"> 6</tt> <tt class="py-line"><tt class="py-docstring">Algorithms and Applications" (Mark de Berg, Marc van Kreveld, Mark Overmars, </tt> </tt> <a name="L7"></a><tt class="py-lineno"> 7</tt> <tt class="py-line"><tt class="py-docstring">Otfried Schwarzkopf). Author: Thomas Hamelryck.</tt> </tt> <a name="L8"></a><tt class="py-lineno"> 8</tt> <tt class="py-line"><tt class="py-docstring">"""</tt> </tt> <a name="L9"></a><tt class="py-lineno"> 9</tt> <tt class="py-line"> </tt> <a name="L10"></a><tt class="py-lineno"> 10</tt> <tt class="py-line"><tt class="py-keyword">try</tt><tt class="py-op">:</tt> </tt> <a name="L11"></a><tt class="py-lineno"> 11</tt> <tt class="py-line"> <tt class="py-keyword">import</tt> <tt class="py-name">Numeric</tt> </tt> <a name="L12"></a><tt class="py-lineno"> 12</tt> <tt class="py-line"> <tt class="py-keyword">from</tt> <tt class="py-name">Numeric</tt> <tt class="py-keyword">import</tt> <tt id="link-0" class="py-name" targets="Method Bio.Nexus.Nexus.StepMatrix.sum()=Bio.Nexus.Nexus.StepMatrix-class.html#sum,Function Bio.utils.sum()=Bio.utils-module.html#sum"><a title="Bio.Nexus.Nexus.StepMatrix.sum Bio.utils.sum" class="py-name" href="#" onclick="return doclink('link-0', 'sum', 'link-0');">sum</a></tt><tt class="py-op">,</tt> <tt id="link-1" class="py-name" targets="Variable Bio.Affy.CelFile.sqrt=Bio.Affy.CelFile-module.html#sqrt,Variable Bio.LogisticRegression.sqrt=Bio.LogisticRegression-module.html#sqrt,Variable Bio.MarkovModel.sqrt=Bio.MarkovModel-module.html#sqrt,Variable Bio.MaxEntropy.sqrt=Bio.MaxEntropy-module.html#sqrt,Variable Bio.NaiveBayes.sqrt=Bio.NaiveBayes-module.html#sqrt,Variable Bio.PDB.ResidueDepth'.sqrt=Bio.PDB.ResidueDepth%27-module.html#sqrt,Variable Bio.PDB.Vector'.sqrt=Bio.PDB.Vector%27-module.html#sqrt,Variable Bio.SVDSuperimposer.SVDSuperimposer'.sqrt=Bio.SVDSuperimposer.SVDSuperimposer%27-module.html#sqrt,Variable Bio.SVDSuperimposer.sqrt=Bio.SVDSuperimposer-module.html#sqrt,Variable Bio.Statistics.lowess.sqrt=Bio.Statistics.lowess-module.html#sqrt,Variable Bio.distance.sqrt=Bio.distance-module.html#sqrt,Variable Bio.kNN.sqrt=Bio.kNN-module.html#sqrt"><a title="Bio.Affy.CelFile.sqrt Bio.LogisticRegression.sqrt Bio.MarkovModel.sqrt Bio.MaxEntropy.sqrt Bio.NaiveBayes.sqrt Bio.PDB.ResidueDepth'.sqrt Bio.PDB.Vector'.sqrt Bio.SVDSuperimposer.SVDSuperimposer'.sqrt Bio.SVDSuperimposer.sqrt Bio.Statistics.lowess.sqrt Bio.distance.sqrt Bio.kNN.sqrt" class="py-name" href="#" onclick="return doclink('link-1', 'sqrt', 'link-1');">sqrt</a></tt> </tt> <a name="L13"></a><tt class="py-lineno"> 13</tt> <tt class="py-line"> <tt class="py-keyword">from</tt> <tt class="py-name">RandomArray</tt> <tt class="py-keyword">import</tt> <tt class="py-op">*</tt> </tt> <a name="L14"></a><tt class="py-lineno"> 14</tt> <tt class="py-line"><tt class="py-keyword">except</tt> <tt class="py-name">ImportError</tt><tt class="py-op">:</tt> </tt> <a name="L15"></a><tt class="py-lineno"> 15</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">ImportError</tt><tt class="py-op">,</tt> <tt class="py-string">"This module requires Numeric (precursor to NumPy)"</tt> </tt> <a name="L16"></a><tt class="py-lineno"> 16</tt> <tt class="py-line"> </tt> <a name="L17"></a><tt class="py-lineno"> 17</tt> <tt class="py-line"><tt class="py-keyword">import</tt> <tt id="link-2" class="py-name" targets="Module Bio.KDTree.CKDTree=Bio.KDTree.CKDTree-module.html"><a title="Bio.KDTree.CKDTree" class="py-name" href="#" onclick="return doclink('link-2', 'CKDTree', 'link-2');">CKDTree</a></tt> </tt> <a name="L18"></a><tt class="py-lineno"> 18</tt> <tt class="py-line"> </tt> <a name="_dist"></a><div id="_dist-def"><a name="L19"></a><tt class="py-lineno"> 19</tt> <a class="py-toggle" href="#" id="_dist-toggle" onclick="return toggle('_dist');">-</a><tt class="py-line"><tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree-module.html#_dist">_dist</a><tt class="py-op">(</tt><tt class="py-param">p</tt><tt class="py-op">,</tt> <tt class="py-param">q</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="_dist-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="_dist-expanded"><a name="L20"></a><tt class="py-lineno"> 20</tt> <tt class="py-line"> <tt class="py-name">diff</tt><tt class="py-op">=</tt><tt class="py-name">p</tt><tt class="py-op">-</tt><tt class="py-name">q</tt> </tt> <a name="L21"></a><tt class="py-lineno"> 21</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt id="link-3" class="py-name"><a title="Bio.Affy.CelFile.sqrt Bio.LogisticRegression.sqrt Bio.MarkovModel.sqrt Bio.MaxEntropy.sqrt Bio.NaiveBayes.sqrt Bio.PDB.ResidueDepth'.sqrt Bio.PDB.Vector'.sqrt Bio.SVDSuperimposer.SVDSuperimposer'.sqrt Bio.SVDSuperimposer.sqrt Bio.Statistics.lowess.sqrt Bio.distance.sqrt Bio.kNN.sqrt" class="py-name" href="#" onclick="return doclink('link-3', 'sqrt', 'link-1');">sqrt</a></tt><tt class="py-op">(</tt><tt id="link-4" class="py-name"><a title="Bio.Nexus.Nexus.StepMatrix.sum Bio.utils.sum" class="py-name" href="#" onclick="return doclink('link-4', 'sum', 'link-0');">sum</a></tt><tt class="py-op">(</tt><tt class="py-name">diff</tt><tt class="py-op">*</tt><tt class="py-name">diff</tt><tt class="py-op">)</tt><tt class="py-op">)</tt> </tt> </div><a name="L22"></a><tt class="py-lineno"> 22</tt> <tt class="py-line"> </tt> <a name="_neighbor_test"></a><div id="_neighbor_test-def"><a name="L23"></a><tt class="py-lineno"> 23</tt> <a class="py-toggle" href="#" id="_neighbor_test-toggle" onclick="return toggle('_neighbor_test');">-</a><tt class="py-line"><tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree-module.html#_neighbor_test">_neighbor_test</a><tt class="py-op">(</tt><tt class="py-param">nr_points</tt><tt class="py-op">,</tt> <tt class="py-param">dim</tt><tt class="py-op">,</tt> <tt class="py-param">bucket_size</tt><tt class="py-op">,</tt> <tt class="py-param">radius</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="_neighbor_test-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="_neighbor_test-expanded"><a name="L24"></a><tt class="py-lineno"> 24</tt> <tt class="py-line"> <tt class="py-docstring">""" Test all fixed radius neighbor search.</tt> </tt> <a name="L25"></a><tt class="py-lineno"> 25</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L26"></a><tt class="py-lineno"> 26</tt> <tt class="py-line"><tt class="py-docstring"> Test all fixed radius neighbor search using the </tt> </tt> <a name="L27"></a><tt class="py-lineno"> 27</tt> <tt class="py-line"><tt class="py-docstring"> KD tree C module.</tt> </tt> <a name="L28"></a><tt class="py-lineno"> 28</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L29"></a><tt class="py-lineno"> 29</tt> <tt class="py-line"><tt class="py-docstring"> o nr_points - number of points used in test</tt> </tt> <a name="L30"></a><tt class="py-lineno"> 30</tt> <tt class="py-line"><tt class="py-docstring"> o dim - dimension of coords</tt> </tt> <a name="L31"></a><tt class="py-lineno"> 31</tt> <tt class="py-line"><tt class="py-docstring"> o bucket_size - nr of points per tree node</tt> </tt> <a name="L32"></a><tt class="py-lineno"> 32</tt> <tt class="py-line"><tt class="py-docstring"> o radius - radius of search (typically 0.05 or so) </tt> </tt> <a name="L33"></a><tt class="py-lineno"> 33</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L34"></a><tt class="py-lineno"> 34</tt> <tt class="py-line"> <tt class="py-comment"># KD tree search</tt> </tt> <a name="L35"></a><tt class="py-lineno"> 35</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">kdt</tt><tt class="py-op">=</tt><tt id="link-5" class="py-name"><a title="Bio.KDTree.CKDTree" class="py-name" href="#" onclick="return doclink('link-5', 'CKDTree', 'link-2');">CKDTree</a></tt><tt class="py-op">.</tt><tt id="link-6" class="py-name" targets="Package Bio.KDTree=Bio.KDTree-module.html,Class Bio.KDTree.CKDTree.KDTree=Bio.KDTree.CKDTree.KDTree-class.html,Module Bio.KDTree.KDTree=Bio.KDTree.KDTree-module.html,Class Bio.KDTree.KDTree.KDTree=Bio.KDTree.KDTree.KDTree-class.html"><a title="Bio.KDTree Bio.KDTree.CKDTree.KDTree Bio.KDTree.KDTree Bio.KDTree.KDTree.KDTree" class="py-name" href="#" onclick="return doclink('link-6', 'KDTree', 'link-6');">KDTree</a></tt><tt class="py-op">(</tt><tt class="py-name">dim</tt><tt class="py-op">,</tt> <tt class="py-name">bucket_size</tt><tt class="py-op">)</tt> </tt> <a name="L36"></a><tt class="py-lineno"> 36</tt> <tt class="py-line"> <tt class="py-name">coords</tt><tt class="py-op">=</tt><tt class="py-name">random</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">nr_points</tt><tt class="py-op">,</tt> <tt class="py-name">dim</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt class="py-name">astype</tt><tt class="py-op">(</tt><tt class="py-string">"f"</tt><tt class="py-op">)</tt> </tt> <a name="L37"></a><tt class="py-lineno"> 37</tt> <tt class="py-line"> <tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-7" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.set_data()=Bio.KDTree.CKDTree.KDTree-class.html#set_data,Method Bio.Nexus.Nodes.Node.set_data()=Bio.Nexus.Nodes.Node-class.html#set_data"><a title="Bio.KDTree.CKDTree.KDTree.set_data Bio.Nexus.Nodes.Node.set_data" class="py-name" href="#" onclick="return doclink('link-7', 'set_data', 'link-7');">set_data</a></tt><tt class="py-op">(</tt><tt class="py-name">coords</tt><tt class="py-op">,</tt> <tt class="py-name">nr_points</tt><tt class="py-op">)</tt> </tt> <a name="L38"></a><tt class="py-lineno"> 38</tt> <tt class="py-line"> <tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-8" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.neighbor_search()=Bio.KDTree.CKDTree.KDTree-class.html#neighbor_search"><a title="Bio.KDTree.CKDTree.KDTree.neighbor_search" class="py-name" href="#" onclick="return doclink('link-8', 'neighbor_search', 'link-8');">neighbor_search</a></tt><tt class="py-op">(</tt><tt class="py-name">radius</tt><tt class="py-op">)</tt> </tt> <a name="L39"></a><tt class="py-lineno"> 39</tt> <tt class="py-line"> <tt class="py-name">r</tt><tt class="py-op">=</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-9" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.neighbor_get_radii()=Bio.KDTree.CKDTree.KDTree-class.html#neighbor_get_radii"><a title="Bio.KDTree.CKDTree.KDTree.neighbor_get_radii" class="py-name" href="#" onclick="return doclink('link-9', 'neighbor_get_radii', 'link-9');">neighbor_get_radii</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L40"></a><tt class="py-lineno"> 40</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt> <a name="L41"></a><tt class="py-lineno"> 41</tt> <tt class="py-line"> <tt class="py-name">l1</tt><tt class="py-op">=</tt><tt class="py-number">0</tt> </tt> <a name="L42"></a><tt class="py-lineno"> 42</tt> <tt class="py-line"> <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt> <a name="L43"></a><tt class="py-lineno"> 43</tt> <tt class="py-line"> <tt class="py-name">l1</tt><tt class="py-op">=</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">r</tt><tt class="py-op">)</tt> </tt> <a name="L44"></a><tt class="py-lineno"> 44</tt> <tt class="py-line"> <tt class="py-comment"># now do a slow search to compare results</tt> </tt> <a name="L45"></a><tt class="py-lineno"> 45</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-10" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.neighbor_simple_search()=Bio.KDTree.CKDTree.KDTree-class.html#neighbor_simple_search"><a title="Bio.KDTree.CKDTree.KDTree.neighbor_simple_search" class="py-name" href="#" onclick="return doclink('link-10', 'neighbor_simple_search', 'link-10');">neighbor_simple_search</a></tt><tt class="py-op">(</tt><tt class="py-name">radius</tt><tt class="py-op">)</tt> </tt> <a name="L46"></a><tt class="py-lineno"> 46</tt> <tt class="py-line"> <tt class="py-name">r</tt><tt class="py-op">=</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-11" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.neighbor_get_radii" class="py-name" href="#" onclick="return doclink('link-11', 'neighbor_get_radii', 'link-9');">neighbor_get_radii</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L47"></a><tt class="py-lineno"> 47</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt> <a name="L48"></a><tt class="py-lineno"> 48</tt> <tt class="py-line"> <tt class="py-name">l2</tt><tt class="py-op">=</tt><tt class="py-number">0</tt> </tt> <a name="L49"></a><tt class="py-lineno"> 49</tt> <tt class="py-line"> <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt> <a name="L50"></a><tt class="py-lineno"> 50</tt> <tt class="py-line"> <tt class="py-name">l2</tt><tt class="py-op">=</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">r</tt><tt class="py-op">)</tt> </tt> <a name="L51"></a><tt class="py-lineno"> 51</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">l1</tt><tt class="py-op">==</tt><tt class="py-name">l2</tt><tt class="py-op">:</tt> </tt> <a name="L52"></a><tt class="py-lineno"> 52</tt> <tt class="py-line"> <tt class="py-keyword">print</tt> <tt class="py-string">"Passed."</tt> </tt> <a name="L53"></a><tt class="py-lineno"> 53</tt> <tt class="py-line"> <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt> <a name="L54"></a><tt class="py-lineno"> 54</tt> <tt class="py-line"> <tt class="py-keyword">print</tt> <tt class="py-string">"Not passed: %i <> %i."</tt> <tt class="py-op">%</tt> <tt class="py-op">(</tt><tt class="py-name">l1</tt><tt class="py-op">,</tt> <tt class="py-name">l2</tt><tt class="py-op">)</tt> </tt> </div><a name="L55"></a><tt class="py-lineno"> 55</tt> <tt class="py-line"> </tt> <a name="_test"></a><div id="_test-def"><a name="L56"></a><tt class="py-lineno"> 56</tt> <a class="py-toggle" href="#" id="_test-toggle" onclick="return toggle('_test');">-</a><tt class="py-line"><tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree-module.html#_test">_test</a><tt class="py-op">(</tt><tt class="py-param">nr_points</tt><tt class="py-op">,</tt> <tt class="py-param">dim</tt><tt class="py-op">,</tt> <tt class="py-param">bucket_size</tt><tt class="py-op">,</tt> <tt class="py-param">radius</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="_test-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="_test-expanded"><a name="L57"></a><tt class="py-lineno"> 57</tt> <tt class="py-line"> <tt class="py-docstring">"""Test neighbor search.</tt> </tt> <a name="L58"></a><tt class="py-lineno"> 58</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L59"></a><tt class="py-lineno"> 59</tt> <tt class="py-line"><tt class="py-docstring"> Test neighbor search using the KD tree C module.</tt> </tt> <a name="L60"></a><tt class="py-lineno"> 60</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L61"></a><tt class="py-lineno"> 61</tt> <tt class="py-line"><tt class="py-docstring"> o nr_points - number of points used in test</tt> </tt> <a name="L62"></a><tt class="py-lineno"> 62</tt> <tt class="py-line"><tt class="py-docstring"> o dim - dimension of coords</tt> </tt> <a name="L63"></a><tt class="py-lineno"> 63</tt> <tt class="py-line"><tt class="py-docstring"> o bucket_size - nr of points per tree node</tt> </tt> <a name="L64"></a><tt class="py-lineno"> 64</tt> <tt class="py-line"><tt class="py-docstring"> o radius - radius of search (typically 0.05 or so) </tt> </tt> <a name="L65"></a><tt class="py-lineno"> 65</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L66"></a><tt class="py-lineno"> 66</tt> <tt class="py-line"> <tt class="py-comment"># kd tree search</tt> </tt> <a name="L67"></a><tt class="py-lineno"> 67</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">kdt</tt><tt class="py-op">=</tt><tt id="link-12" class="py-name"><a title="Bio.KDTree.CKDTree" class="py-name" href="#" onclick="return doclink('link-12', 'CKDTree', 'link-2');">CKDTree</a></tt><tt class="py-op">.</tt><tt id="link-13" class="py-name"><a title="Bio.KDTree Bio.KDTree.CKDTree.KDTree Bio.KDTree.KDTree Bio.KDTree.KDTree.KDTree" class="py-name" href="#" onclick="return doclink('link-13', 'KDTree', 'link-6');">KDTree</a></tt><tt class="py-op">(</tt><tt class="py-name">dim</tt><tt class="py-op">,</tt> <tt class="py-name">bucket_size</tt><tt class="py-op">)</tt> </tt> <a name="L68"></a><tt class="py-lineno"> 68</tt> <tt class="py-line"> <tt class="py-name">coords</tt><tt class="py-op">=</tt><tt class="py-name">random</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">nr_points</tt><tt class="py-op">,</tt> <tt class="py-name">dim</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt class="py-name">astype</tt><tt class="py-op">(</tt><tt class="py-string">"f"</tt><tt class="py-op">)</tt> </tt> <a name="L69"></a><tt class="py-lineno"> 69</tt> <tt class="py-line"> <tt class="py-name">center</tt><tt class="py-op">=</tt><tt class="py-name">coords</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt> </tt> <a name="L70"></a><tt class="py-lineno"> 70</tt> <tt class="py-line"> <tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-14" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.set_data Bio.Nexus.Nodes.Node.set_data" class="py-name" href="#" onclick="return doclink('link-14', 'set_data', 'link-7');">set_data</a></tt><tt class="py-op">(</tt><tt class="py-name">coords</tt><tt class="py-op">,</tt> <tt class="py-name">nr_points</tt><tt class="py-op">)</tt> </tt> <a name="L71"></a><tt class="py-lineno"> 71</tt> <tt class="py-line"> <tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-15" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.search_center_radius()=Bio.KDTree.CKDTree.KDTree-class.html#search_center_radius"><a title="Bio.KDTree.CKDTree.KDTree.search_center_radius" class="py-name" href="#" onclick="return doclink('link-15', 'search_center_radius', 'link-15');">search_center_radius</a></tt><tt class="py-op">(</tt><tt class="py-name">center</tt><tt class="py-op">,</tt> <tt class="py-name">radius</tt><tt class="py-op">)</tt> </tt> <a name="L72"></a><tt class="py-lineno"> 72</tt> <tt class="py-line"> <tt class="py-name">r</tt><tt class="py-op">=</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-16" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.get_indices()=Bio.KDTree.CKDTree.KDTree-class.html#get_indices,Method Bio.KDTree.KDTree.KDTree.get_indices()=Bio.KDTree.KDTree.KDTree-class.html#get_indices"><a title="Bio.KDTree.CKDTree.KDTree.get_indices Bio.KDTree.KDTree.KDTree.get_indices" class="py-name" href="#" onclick="return doclink('link-16', 'get_indices', 'link-16');">get_indices</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L73"></a><tt class="py-lineno"> 73</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">r</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt> <a name="L74"></a><tt class="py-lineno"> 74</tt> <tt class="py-line"> <tt class="py-name">l1</tt><tt class="py-op">=</tt><tt class="py-number">0</tt> </tt> <a name="L75"></a><tt class="py-lineno"> 75</tt> <tt class="py-line"> <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt> <a name="L76"></a><tt class="py-lineno"> 76</tt> <tt class="py-line"> <tt class="py-name">l1</tt><tt class="py-op">=</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">r</tt><tt class="py-op">)</tt> </tt> <a name="L77"></a><tt class="py-lineno"> 77</tt> <tt class="py-line"> <tt class="py-name">l2</tt><tt class="py-op">=</tt><tt class="py-number">0</tt> </tt> <a name="L78"></a><tt class="py-lineno"> 78</tt> <tt class="py-line"> <tt class="py-comment"># now do a manual search to compare results</tt> </tt> <a name="L79"></a><tt class="py-lineno"> 79</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-keyword">for</tt> <tt id="link-17" class="py-name" targets="Variable Bio.PDB.Polypeptide.i=Bio.PDB.Polypeptide-module.html#i"><a title="Bio.PDB.Polypeptide.i" class="py-name" href="#" onclick="return doclink('link-17', 'i', 'link-17');">i</a></tt> <tt class="py-keyword">in</tt> <tt class="py-name">range</tt><tt class="py-op">(</tt><tt class="py-number">0</tt><tt class="py-op">,</tt> <tt class="py-name">nr_points</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> <a name="L80"></a><tt class="py-lineno"> 80</tt> <tt class="py-line"> <tt class="py-name">p</tt><tt class="py-op">=</tt><tt class="py-name">coords</tt><tt class="py-op">[</tt><tt id="link-18" class="py-name"><a title="Bio.PDB.Polypeptide.i" class="py-name" href="#" onclick="return doclink('link-18', 'i', 'link-17');">i</a></tt><tt class="py-op">]</tt> </tt> <a name="L81"></a><tt class="py-lineno"> 81</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">_dist</tt><tt class="py-op">(</tt><tt class="py-name">p</tt><tt class="py-op">,</tt> <tt class="py-name">center</tt><tt class="py-op">)</tt><tt class="py-op"><=</tt><tt class="py-name">radius</tt><tt class="py-op">:</tt> </tt> <a name="L82"></a><tt class="py-lineno"> 82</tt> <tt class="py-line"> <tt class="py-name">l2</tt><tt class="py-op">=</tt><tt class="py-name">l2</tt><tt class="py-op">+</tt><tt class="py-number">1</tt> </tt> <a name="L83"></a><tt class="py-lineno"> 83</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">l1</tt><tt class="py-op">==</tt><tt class="py-name">l2</tt><tt class="py-op">:</tt> </tt> <a name="L84"></a><tt class="py-lineno"> 84</tt> <tt class="py-line"> <tt class="py-keyword">print</tt> <tt class="py-string">"Passed."</tt> </tt> <a name="L85"></a><tt class="py-lineno"> 85</tt> <tt class="py-line"> <tt class="py-keyword">else</tt><tt class="py-op">:</tt> </tt> <a name="L86"></a><tt class="py-lineno"> 86</tt> <tt class="py-line"> <tt class="py-keyword">print</tt> <tt class="py-string">"Not passed: %i <> %i."</tt> <tt class="py-op">%</tt> <tt class="py-op">(</tt><tt class="py-name">l1</tt><tt class="py-op">,</tt> <tt class="py-name">l2</tt><tt class="py-op">)</tt> </tt> </div><a name="L87"></a><tt class="py-lineno"> 87</tt> <tt class="py-line"> </tt> <a name="KDTree"></a><div id="KDTree-def"><a name="L88"></a><tt class="py-lineno"> 88</tt> <a class="py-toggle" href="#" id="KDTree-toggle" onclick="return toggle('KDTree');">-</a><tt class="py-line"><tt class="py-keyword">class</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html">KDTree</a><tt class="py-op">:</tt> </tt> </div><div id="KDTree-collapsed" style="display:none;" pad="+++" indent="++++"></div><div id="KDTree-expanded"><a name="L89"></a><tt class="py-lineno"> 89</tt> <tt class="py-line"> <tt class="py-docstring">"""</tt> </tt> <a name="L90"></a><tt class="py-lineno"> 90</tt> <tt class="py-line"><tt class="py-docstring"> KD tree implementation (C++, SWIG python wrapper)</tt> </tt> <a name="L91"></a><tt class="py-lineno"> 91</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L92"></a><tt class="py-lineno"> 92</tt> <tt class="py-line"><tt class="py-docstring"> The KD tree data structure can be used for all kinds of searches that</tt> </tt> <a name="L93"></a><tt class="py-lineno"> 93</tt> <tt class="py-line"><tt class="py-docstring"> involve N-dimensional vectors, e.g. neighbor searches (find all points</tt> </tt> <a name="L94"></a><tt class="py-lineno"> 94</tt> <tt class="py-line"><tt class="py-docstring"> within a radius of a given point) or finding all point pairs in a set</tt> </tt> <a name="L95"></a><tt class="py-lineno"> 95</tt> <tt class="py-line"><tt class="py-docstring"> that are within a certain radius of each other.</tt> </tt> <a name="L96"></a><tt class="py-lineno"> 96</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L97"></a><tt class="py-lineno"> 97</tt> <tt class="py-line"><tt class="py-docstring"> Reference:</tt> </tt> <a name="L98"></a><tt class="py-lineno"> 98</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L99"></a><tt class="py-lineno"> 99</tt> <tt class="py-line"><tt class="py-docstring"> Computational Geometry: Algorithms and Applications</tt> </tt> <a name="L100"></a><tt class="py-lineno">100</tt> <tt class="py-line"><tt class="py-docstring"> Second Edition</tt> </tt> <a name="L101"></a><tt class="py-lineno">101</tt> <tt class="py-line"><tt class="py-docstring"> Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf</tt> </tt> <a name="L102"></a><tt class="py-lineno">102</tt> <tt class="py-line"><tt class="py-docstring"> published by Springer-Verlag</tt> </tt> <a name="L103"></a><tt class="py-lineno">103</tt> <tt class="py-line"><tt class="py-docstring"> 2nd rev. ed. 2000. </tt> </tt> <a name="L104"></a><tt class="py-lineno">104</tt> <tt class="py-line"><tt class="py-docstring"> ISBN: 3-540-65620-0</tt> </tt> <a name="L105"></a><tt class="py-lineno">105</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L106"></a><tt class="py-lineno">106</tt> <tt class="py-line"><tt class="py-docstring"> The KD tree data structure is described in chapter 5, pg. 99. </tt> </tt> <a name="L107"></a><tt class="py-lineno">107</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L108"></a><tt class="py-lineno">108</tt> <tt class="py-line"><tt class="py-docstring"> The following article made clear to me that the nodes should </tt> </tt> <a name="L109"></a><tt class="py-lineno">109</tt> <tt class="py-line"><tt class="py-docstring"> contain more than one point (this leads to dramatic speed </tt> </tt> <a name="L110"></a><tt class="py-lineno">110</tt> <tt class="py-line"><tt class="py-docstring"> improvements for the "all fixed radius neighbor search", see</tt> </tt> <a name="L111"></a><tt class="py-lineno">111</tt> <tt class="py-line"><tt class="py-docstring"> below):</tt> </tt> <a name="L112"></a><tt class="py-lineno">112</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L113"></a><tt class="py-lineno">113</tt> <tt class="py-line"><tt class="py-docstring"> JL Bentley, "Kd trees for semidynamic point sets," in Sixth Annual ACM</tt> </tt> <a name="L114"></a><tt class="py-lineno">114</tt> <tt class="py-line"><tt class="py-docstring"> Symposium on Computational Geometry, vol. 91. San Francisco, 1990</tt> </tt> <a name="L115"></a><tt class="py-lineno">115</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L116"></a><tt class="py-lineno">116</tt> <tt class="py-line"><tt class="py-docstring"> This KD implementation also performs a "all fixed radius neighbor search",</tt> </tt> <a name="L117"></a><tt class="py-lineno">117</tt> <tt class="py-line"><tt class="py-docstring"> i.e. it can find all point pairs in a set that are within a certain radius</tt> </tt> <a name="L118"></a><tt class="py-lineno">118</tt> <tt class="py-line"><tt class="py-docstring"> of each other. As far as I know the algorithm has not been published.</tt> </tt> <a name="L119"></a><tt class="py-lineno">119</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L120"></a><tt class="py-lineno">120</tt> <tt class="py-line"> </tt> <a name="KDTree.__init__"></a><div id="KDTree.__init__-def"><a name="L121"></a><tt class="py-lineno">121</tt> <a class="py-toggle" href="#" id="KDTree.__init__-toggle" onclick="return toggle('KDTree.__init__');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#__init__">__init__</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">dim</tt><tt class="py-op">,</tt> <tt class="py-param">bucket_size</tt><tt class="py-op">=</tt><tt class="py-number">1</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.__init__-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.__init__-expanded"><a name="L122"></a><tt class="py-lineno">122</tt> <tt class="py-line"> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">dim</tt><tt class="py-op">=</tt><tt class="py-name">dim</tt> </tt> <a name="L123"></a><tt class="py-lineno">123</tt> <tt class="py-line"> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">=</tt><tt id="link-19" class="py-name"><a title="Bio.KDTree.CKDTree" class="py-name" href="#" onclick="return doclink('link-19', 'CKDTree', 'link-2');">CKDTree</a></tt><tt class="py-op">.</tt><tt id="link-20" class="py-name"><a title="Bio.KDTree Bio.KDTree.CKDTree.KDTree Bio.KDTree.KDTree Bio.KDTree.KDTree.KDTree" class="py-name" href="#" onclick="return doclink('link-20', 'KDTree', 'link-6');">KDTree</a></tt><tt class="py-op">(</tt><tt class="py-name">dim</tt><tt class="py-op">,</tt> <tt class="py-name">bucket_size</tt><tt class="py-op">)</tt> </tt> <a name="L124"></a><tt class="py-lineno">124</tt> <tt class="py-line"> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">built</tt><tt class="py-op">=</tt><tt class="py-number">0</tt> </tt> </div><a name="L125"></a><tt class="py-lineno">125</tt> <tt class="py-line"> </tt> <a name="L126"></a><tt class="py-lineno">126</tt> <tt class="py-line"> <tt class="py-comment"># Set data</tt> </tt> <a name="L127"></a><tt class="py-lineno">127</tt> <tt class="py-line"><tt class="py-comment"></tt> </tt> <a name="KDTree.set_coords"></a><div id="KDTree.set_coords-def"><a name="L128"></a><tt class="py-lineno">128</tt> <a class="py-toggle" href="#" id="KDTree.set_coords-toggle" onclick="return toggle('KDTree.set_coords');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#set_coords">set_coords</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">coords</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.set_coords-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.set_coords-expanded"><a name="L129"></a><tt class="py-lineno">129</tt> <tt class="py-line"> <tt class="py-docstring">"""Add the coordinates of the points.</tt> </tt> <a name="L130"></a><tt class="py-lineno">130</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L131"></a><tt class="py-lineno">131</tt> <tt class="py-line"><tt class="py-docstring"> o coords - two dimensional Numeric array of type "f". E.g. if the </tt> </tt> <a name="L132"></a><tt class="py-lineno">132</tt> <tt class="py-line"><tt class="py-docstring"> points have dimensionality D and there are N points, the coords </tt> </tt> <a name="L133"></a><tt class="py-lineno">133</tt> <tt class="py-line"><tt class="py-docstring"> array should be NxD dimensional. </tt> </tt> <a name="L134"></a><tt class="py-lineno">134</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L135"></a><tt class="py-lineno">135</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">min</tt><tt class="py-op">(</tt><tt class="py-name">coords</tt><tt class="py-op">)</tt><tt class="py-op"><=</tt><tt class="py-op">-</tt><tt class="py-number">1e6</tt> <tt class="py-keyword">or</tt> <tt class="py-name">max</tt><tt class="py-op">(</tt><tt class="py-name">coords</tt><tt class="py-op">)</tt><tt class="py-op">>=</tt><tt class="py-number">1e6</tt><tt class="py-op">:</tt> </tt> <a name="L136"></a><tt class="py-lineno">136</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">Exception</tt><tt class="py-op">,</tt> <tt class="py-string">"Points should lie between -1e6 and 1e6"</tt> </tt> <a name="L137"></a><tt class="py-lineno">137</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">coords</tt><tt class="py-op">.</tt><tt class="py-name">shape</tt><tt class="py-op">)</tt><tt class="py-op">!=</tt><tt class="py-number">2</tt> <tt class="py-keyword">or</tt> <tt class="py-name">coords</tt><tt class="py-op">.</tt><tt class="py-name">shape</tt><tt class="py-op">[</tt><tt class="py-number">1</tt><tt class="py-op">]</tt><tt class="py-op">!=</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">dim</tt><tt class="py-op">:</tt> </tt> <a name="L138"></a><tt class="py-lineno">138</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">Exception</tt><tt class="py-op">,</tt> <tt class="py-string">"Expected a Nx%i Numeric array"</tt> <tt class="py-op">%</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">dim</tt> </tt> <a name="L139"></a><tt class="py-lineno">139</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">coords</tt><tt class="py-op">.</tt><tt class="py-name">typecode</tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">!=</tt><tt class="py-string">"f"</tt><tt class="py-op">:</tt> </tt> <a name="L140"></a><tt class="py-lineno">140</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">Exception</tt><tt class="py-op">,</tt> <tt class="py-string">"Expected a Numeric array of type float"</tt> </tt> <a name="L141"></a><tt class="py-lineno">141</tt> <tt class="py-line"> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-21" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.set_data Bio.Nexus.Nodes.Node.set_data" class="py-name" href="#" onclick="return doclink('link-21', 'set_data', 'link-7');">set_data</a></tt><tt class="py-op">(</tt><tt class="py-name">coords</tt><tt class="py-op">,</tt> <tt class="py-name">coords</tt><tt class="py-op">.</tt><tt class="py-name">shape</tt><tt class="py-op">[</tt><tt class="py-number">0</tt><tt class="py-op">]</tt><tt class="py-op">)</tt> </tt> <a name="L142"></a><tt class="py-lineno">142</tt> <tt class="py-line"> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">built</tt><tt class="py-op">=</tt><tt class="py-number">1</tt> </tt> </div><a name="L143"></a><tt class="py-lineno">143</tt> <tt class="py-line"> </tt> <a name="L144"></a><tt class="py-lineno">144</tt> <tt class="py-line"> <tt class="py-comment"># Fixed radius search for a point</tt> </tt> <a name="L145"></a><tt class="py-lineno">145</tt> <tt class="py-line"><tt class="py-comment"></tt> </tt> <a name="KDTree.search"></a><div id="KDTree.search-def"><a name="L146"></a><tt class="py-lineno">146</tt> <a class="py-toggle" href="#" id="KDTree.search-toggle" onclick="return toggle('KDTree.search');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#search">search</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">center</tt><tt class="py-op">,</tt> <tt class="py-param">radius</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.search-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.search-expanded"><a name="L147"></a><tt class="py-lineno">147</tt> <tt class="py-line"> <tt class="py-docstring">"""Search all points within radius of center.</tt> </tt> <a name="L148"></a><tt class="py-lineno">148</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L149"></a><tt class="py-lineno">149</tt> <tt class="py-line"><tt class="py-docstring"> o center - one dimensional Numeric array of type "f". E.g. if the </tt> </tt> <a name="L150"></a><tt class="py-lineno">150</tt> <tt class="py-line"><tt class="py-docstring"> points have dimensionality D, the center array should be D </tt> </tt> <a name="L151"></a><tt class="py-lineno">151</tt> <tt class="py-line"><tt class="py-docstring"> dimensional. </tt> </tt> <a name="L152"></a><tt class="py-lineno">152</tt> <tt class="py-line"><tt class="py-docstring"> o radius - float>0</tt> </tt> <a name="L153"></a><tt class="py-lineno">153</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L154"></a><tt class="py-lineno">154</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">built</tt><tt class="py-op">:</tt> </tt> <a name="L155"></a><tt class="py-lineno">155</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">Exception</tt><tt class="py-op">,</tt> <tt class="py-string">"No point set specified"</tt> </tt> <a name="L156"></a><tt class="py-lineno">156</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">center</tt><tt class="py-op">.</tt><tt class="py-name">shape</tt><tt class="py-op">!=</tt><tt class="py-op">(</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">dim</tt><tt class="py-op">,</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> <a name="L157"></a><tt class="py-lineno">157</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">Exception</tt><tt class="py-op">,</tt> <tt class="py-string">"Expected a %i-dimensional Numeric array"</tt> <tt class="py-op">%</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">dim</tt> </tt> <a name="L158"></a><tt class="py-lineno">158</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">center</tt><tt class="py-op">.</tt><tt class="py-name">typecode</tt><tt class="py-op">(</tt><tt class="py-op">)</tt><tt class="py-op">!=</tt><tt class="py-string">"f"</tt><tt class="py-op">:</tt> </tt> <a name="L159"></a><tt class="py-lineno">159</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">Exception</tt><tt class="py-op">,</tt> <tt class="py-string">"Expected a Numeric array of type float"</tt> </tt> <a name="L160"></a><tt class="py-lineno">160</tt> <tt class="py-line"> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-22" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.search_center_radius" class="py-name" href="#" onclick="return doclink('link-22', 'search_center_radius', 'link-15');">search_center_radius</a></tt><tt class="py-op">(</tt><tt class="py-name">center</tt><tt class="py-op">,</tt> <tt class="py-name">radius</tt><tt class="py-op">)</tt> </tt> </div><a name="L161"></a><tt class="py-lineno">161</tt> <tt class="py-line"> </tt> <a name="KDTree.get_radii"></a><div id="KDTree.get_radii-def"><a name="L162"></a><tt class="py-lineno">162</tt> <a class="py-toggle" href="#" id="KDTree.get_radii-toggle" onclick="return toggle('KDTree.get_radii');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#get_radii">get_radii</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.get_radii-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.get_radii-expanded"><a name="L163"></a><tt class="py-lineno">163</tt> <tt class="py-line"> <tt class="py-docstring">"""Return radii.</tt> </tt> <a name="L164"></a><tt class="py-lineno">164</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L165"></a><tt class="py-lineno">165</tt> <tt class="py-line"><tt class="py-docstring"> Return the list of distances from center after</tt> </tt> <a name="L166"></a><tt class="py-lineno">166</tt> <tt class="py-line"><tt class="py-docstring"> a neighbor search.</tt> </tt> <a name="L167"></a><tt class="py-lineno">167</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L168"></a><tt class="py-lineno">168</tt> <tt class="py-line"> <tt class="py-name">a</tt><tt class="py-op">=</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-23" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.get_radii()=Bio.KDTree.CKDTree.KDTree-class.html#get_radii,Method Bio.KDTree.KDTree.KDTree.get_radii()=Bio.KDTree.KDTree.KDTree-class.html#get_radii"><a title="Bio.KDTree.CKDTree.KDTree.get_radii Bio.KDTree.KDTree.KDTree.get_radii" class="py-name" href="#" onclick="return doclink('link-23', 'get_radii', 'link-23');">get_radii</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L169"></a><tt class="py-lineno">169</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">a</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt> <a name="L170"></a><tt class="py-lineno">170</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-op">[</tt><tt class="py-op">]</tt> </tt> <a name="L171"></a><tt class="py-lineno">171</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-name">a</tt> </tt> </div><a name="L172"></a><tt class="py-lineno">172</tt> <tt class="py-line"> </tt> <a name="KDTree.get_indices"></a><div id="KDTree.get_indices-def"><a name="L173"></a><tt class="py-lineno">173</tt> <a class="py-toggle" href="#" id="KDTree.get_indices-toggle" onclick="return toggle('KDTree.get_indices');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#get_indices">get_indices</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.get_indices-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.get_indices-expanded"><a name="L174"></a><tt class="py-lineno">174</tt> <tt class="py-line"> <tt class="py-docstring">"""Return the list of indices.</tt> </tt> <a name="L175"></a><tt class="py-lineno">175</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L176"></a><tt class="py-lineno">176</tt> <tt class="py-line"><tt class="py-docstring"> Return the list of indices after a neighbor search.</tt> </tt> <a name="L177"></a><tt class="py-lineno">177</tt> <tt class="py-line"><tt class="py-docstring"> The indices refer to the original coords Numeric array. The</tt> </tt> <a name="L178"></a><tt class="py-lineno">178</tt> <tt class="py-line"><tt class="py-docstring"> coordinates with these indices were within radius of center.</tt> </tt> <a name="L179"></a><tt class="py-lineno">179</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L180"></a><tt class="py-lineno">180</tt> <tt class="py-line"><tt class="py-docstring"> For an index pair, the first index<second index. </tt> </tt> <a name="L181"></a><tt class="py-lineno">181</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L182"></a><tt class="py-lineno">182</tt> <tt class="py-line"> <tt class="py-name">a</tt><tt class="py-op">=</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-24" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.get_indices Bio.KDTree.KDTree.KDTree.get_indices" class="py-name" href="#" onclick="return doclink('link-24', 'get_indices', 'link-16');">get_indices</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L183"></a><tt class="py-lineno">183</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">a</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt> <a name="L184"></a><tt class="py-lineno">184</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-op">[</tt><tt class="py-op">]</tt> </tt> <a name="L185"></a><tt class="py-lineno">185</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-name">a</tt> </tt> </div><a name="L186"></a><tt class="py-lineno">186</tt> <tt class="py-line"> </tt> <a name="L187"></a><tt class="py-lineno">187</tt> <tt class="py-line"> <tt class="py-comment"># Fixed radius search for all points</tt> </tt> <a name="L188"></a><tt class="py-lineno">188</tt> <tt class="py-line"><tt class="py-comment"></tt> </tt> <a name="L189"></a><tt class="py-lineno">189</tt> <tt class="py-line"> </tt> <a name="KDTree.all_search"></a><div id="KDTree.all_search-def"><a name="L190"></a><tt class="py-lineno">190</tt> <a class="py-toggle" href="#" id="KDTree.all_search-toggle" onclick="return toggle('KDTree.all_search');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#all_search">all_search</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">,</tt> <tt class="py-param">radius</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.all_search-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.all_search-expanded"><a name="L191"></a><tt class="py-lineno">191</tt> <tt class="py-line"> <tt class="py-docstring">"""All fixed neighbor search.</tt> </tt> <a name="L192"></a><tt class="py-lineno">192</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L193"></a><tt class="py-lineno">193</tt> <tt class="py-line"><tt class="py-docstring"> Search all point pairs that are within radius.</tt> </tt> <a name="L194"></a><tt class="py-lineno">194</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L195"></a><tt class="py-lineno">195</tt> <tt class="py-line"><tt class="py-docstring"> o radius - float (>0)</tt> </tt> <a name="L196"></a><tt class="py-lineno">196</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L197"></a><tt class="py-lineno">197</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-keyword">not</tt> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">built</tt><tt class="py-op">:</tt> </tt> <a name="L198"></a><tt class="py-lineno">198</tt> <tt class="py-line"> <tt class="py-keyword">raise</tt> <tt class="py-name">Exception</tt><tt class="py-op">,</tt> <tt class="py-string">"No point set specified"</tt> </tt> <a name="L199"></a><tt class="py-lineno">199</tt> <tt class="py-line"> <tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-25" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.neighbor_search" class="py-name" href="#" onclick="return doclink('link-25', 'neighbor_search', 'link-8');">neighbor_search</a></tt><tt class="py-op">(</tt><tt class="py-name">radius</tt><tt class="py-op">)</tt> </tt> </div><a name="L200"></a><tt class="py-lineno">200</tt> <tt class="py-line"> </tt> <a name="KDTree.all_get_indices"></a><div id="KDTree.all_get_indices-def"><a name="L201"></a><tt class="py-lineno">201</tt> <a class="py-toggle" href="#" id="KDTree.all_get_indices-toggle" onclick="return toggle('KDTree.all_get_indices');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#all_get_indices">all_get_indices</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.all_get_indices-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.all_get_indices-expanded"><a name="L202"></a><tt class="py-lineno">202</tt> <tt class="py-line"> <tt class="py-docstring">"""Return All Fixed Neighbor Search results.</tt> </tt> <a name="L203"></a><tt class="py-lineno">203</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L204"></a><tt class="py-lineno">204</tt> <tt class="py-line"><tt class="py-docstring"> Return a Nx2 dim Numeric array containing</tt> </tt> <a name="L205"></a><tt class="py-lineno">205</tt> <tt class="py-line"><tt class="py-docstring"> the indices of the point pairs, where N</tt> </tt> <a name="L206"></a><tt class="py-lineno">206</tt> <tt class="py-line"><tt class="py-docstring"> is the number of neighbor pairs.</tt> </tt> <a name="L207"></a><tt class="py-lineno">207</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L208"></a><tt class="py-lineno">208</tt> <tt class="py-line"> <tt class="py-name">a</tt><tt class="py-op">=</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-26" class="py-name" targets="Method Bio.KDTree.CKDTree.KDTree.neighbor_get_indices()=Bio.KDTree.CKDTree.KDTree-class.html#neighbor_get_indices"><a title="Bio.KDTree.CKDTree.KDTree.neighbor_get_indices" class="py-name" href="#" onclick="return doclink('link-26', 'neighbor_get_indices', 'link-26');">neighbor_get_indices</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L209"></a><tt class="py-lineno">209</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">a</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt> <a name="L210"></a><tt class="py-lineno">210</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-op">[</tt><tt class="py-op">]</tt> </tt> <a name="L211"></a><tt class="py-lineno">211</tt> <tt class="py-line"> <tt class="py-comment"># return as Nx2 dim Numeric array, where N</tt> </tt> <a name="L212"></a><tt class="py-lineno">212</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-comment"># is number of neighbor pairs.</tt> </tt> <a name="L213"></a><tt class="py-lineno">213</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">a</tt><tt class="py-op">.</tt><tt class="py-name">shape</tt><tt class="py-op">=</tt><tt class="py-op">(</tt><tt class="py-op">-</tt><tt class="py-number">1</tt><tt class="py-op">,</tt> <tt class="py-number">2</tt><tt class="py-op">)</tt> </tt> <a name="L214"></a><tt class="py-lineno">214</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-name">a</tt> </tt> </div><a name="L215"></a><tt class="py-lineno">215</tt> <tt class="py-line"> </tt> <a name="KDTree.all_get_radii"></a><div id="KDTree.all_get_radii-def"><a name="L216"></a><tt class="py-lineno">216</tt> <a class="py-toggle" href="#" id="KDTree.all_get_radii-toggle" onclick="return toggle('KDTree.all_get_radii');">-</a><tt class="py-line"> <tt class="py-keyword">def</tt> <a class="py-def-name" href="Bio.KDTree.KDTree.KDTree-class.html#all_get_radii">all_get_radii</a><tt class="py-op">(</tt><tt class="py-param">self</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> </div><div id="KDTree.all_get_radii-collapsed" style="display:none;" pad="+++" indent="++++++++"></div><div id="KDTree.all_get_radii-expanded"><a name="L217"></a><tt class="py-lineno">217</tt> <tt class="py-line"> <tt class="py-docstring">"""Return All Fixed Neighbor Search results.</tt> </tt> <a name="L218"></a><tt class="py-lineno">218</tt> <tt class="py-line"><tt class="py-docstring"></tt> </tt> <a name="L219"></a><tt class="py-lineno">219</tt> <tt class="py-line"><tt class="py-docstring"> Return an N-dim array containing the distances</tt> </tt> <a name="L220"></a><tt class="py-lineno">220</tt> <tt class="py-line"><tt class="py-docstring"> of all the point pairs, where N is the number </tt> </tt> <a name="L221"></a><tt class="py-lineno">221</tt> <tt class="py-line"><tt class="py-docstring"> of neighbor pairs..</tt> </tt> <a name="L222"></a><tt class="py-lineno">222</tt> <tt class="py-line"><tt class="py-docstring"> """</tt> </tt> <a name="L223"></a><tt class="py-lineno">223</tt> <tt class="py-line"> <tt class="py-name">a</tt><tt class="py-op">=</tt><tt class="py-name">self</tt><tt class="py-op">.</tt><tt class="py-name">kdt</tt><tt class="py-op">.</tt><tt id="link-27" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.neighbor_get_radii" class="py-name" href="#" onclick="return doclink('link-27', 'neighbor_get_radii', 'link-9');">neighbor_get_radii</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L224"></a><tt class="py-lineno">224</tt> <tt class="py-line"> <tt class="py-keyword">if</tt> <tt class="py-name">a</tt> <tt class="py-keyword">is</tt> <tt class="py-name">None</tt><tt class="py-op">:</tt> </tt> <a name="L225"></a><tt class="py-lineno">225</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-op">[</tt><tt class="py-op">]</tt> </tt> <a name="L226"></a><tt class="py-lineno">226</tt> <tt class="py-line"> <tt class="py-keyword">return</tt> <tt class="py-name">a</tt> </tt> </div></div><a name="L227"></a><tt class="py-lineno">227</tt> <tt class="py-line"> </tt> <a name="L228"></a><tt class="py-lineno">228</tt> <tt class="py-line"><tt class="py-keyword">if</tt> <tt class="py-name">__name__</tt><tt class="py-op">==</tt><tt class="py-string">"__main__"</tt><tt class="py-op">:</tt> </tt> <a name="L229"></a><tt class="py-lineno">229</tt> <tt class="py-line"> </tt> <a name="L230"></a><tt class="py-lineno">230</tt> <tt class="py-line"> <tt class="py-keyword">from</tt> <tt class="py-name">RandomArray</tt> <tt class="py-keyword">import</tt> <tt class="py-op">*</tt> </tt> <a name="L231"></a><tt class="py-lineno">231</tt> <tt class="py-line"> </tt> <a name="L232"></a><tt class="py-lineno">232</tt> <tt class="py-line"> <tt class="py-name">nr_points</tt><tt class="py-op">=</tt><tt class="py-number">100000</tt> </tt> <a name="L233"></a><tt class="py-lineno">233</tt> <tt class="py-line"> <tt class="py-name">dim</tt><tt class="py-op">=</tt><tt class="py-number">3</tt> </tt> <a name="L234"></a><tt class="py-lineno">234</tt> <tt class="py-line"> <tt class="py-name">bucket_size</tt><tt class="py-op">=</tt><tt class="py-number">10</tt> </tt> <a name="L235"></a><tt class="py-lineno">235</tt> <tt class="py-line"> <tt class="py-name">query_radius</tt><tt class="py-op">=</tt><tt class="py-number">10</tt> </tt> <a name="L236"></a><tt class="py-lineno">236</tt> <tt class="py-line"> </tt> <a name="L237"></a><tt class="py-lineno">237</tt> <tt class="py-line"> <tt class="py-name">coords</tt><tt class="py-op">=</tt><tt class="py-op">(</tt><tt class="py-number">200</tt><tt class="py-op">*</tt><tt class="py-name">random</tt><tt class="py-op">(</tt><tt class="py-op">(</tt><tt class="py-name">nr_points</tt><tt class="py-op">,</tt> <tt class="py-name">dim</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt class="py-name">astype</tt><tt class="py-op">(</tt><tt class="py-string">"f"</tt><tt class="py-op">)</tt> </tt> <a name="L238"></a><tt class="py-lineno">238</tt> <tt class="py-line"> </tt> <a name="L239"></a><tt class="py-lineno">239</tt> <tt class="py-line"> <tt class="py-name">kdtree</tt><tt class="py-op">=</tt><tt id="link-28" class="py-name"><a title="Bio.KDTree Bio.KDTree.CKDTree.KDTree Bio.KDTree.KDTree Bio.KDTree.KDTree.KDTree" class="py-name" href="#" onclick="return doclink('link-28', 'KDTree', 'link-6');">KDTree</a></tt><tt class="py-op">(</tt><tt class="py-name">dim</tt><tt class="py-op">,</tt> <tt class="py-name">bucket_size</tt><tt class="py-op">)</tt> </tt> <a name="L240"></a><tt class="py-lineno">240</tt> <tt class="py-line"> </tt> <a name="L241"></a><tt class="py-lineno">241</tt> <tt class="py-line"> <tt class="py-comment"># enter coords</tt> </tt> <a name="L242"></a><tt class="py-lineno">242</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">kdtree</tt><tt class="py-op">.</tt><tt id="link-29" class="py-name" targets="Method Bio.KDTree.KDTree.KDTree.set_coords()=Bio.KDTree.KDTree.KDTree-class.html#set_coords"><a title="Bio.KDTree.KDTree.KDTree.set_coords" class="py-name" href="#" onclick="return doclink('link-29', 'set_coords', 'link-29');">set_coords</a></tt><tt class="py-op">(</tt><tt class="py-name">coords</tt><tt class="py-op">)</tt> </tt> <a name="L243"></a><tt class="py-lineno">243</tt> <tt class="py-line"> </tt> <a name="L244"></a><tt class="py-lineno">244</tt> <tt class="py-line"> <tt class="py-comment"># Find all point pairs within radius</tt> </tt> <a name="L245"></a><tt class="py-lineno">245</tt> <tt class="py-line"><tt class="py-comment"></tt> </tt> <a name="L246"></a><tt class="py-lineno">246</tt> <tt class="py-line"> <tt class="py-name">kdtree</tt><tt class="py-op">.</tt><tt id="link-30" class="py-name" targets="Method Bio.KDTree.KDTree.KDTree.all_search()=Bio.KDTree.KDTree.KDTree-class.html#all_search"><a title="Bio.KDTree.KDTree.KDTree.all_search" class="py-name" href="#" onclick="return doclink('link-30', 'all_search', 'link-30');">all_search</a></tt><tt class="py-op">(</tt><tt class="py-name">query_radius</tt><tt class="py-op">)</tt> </tt> <a name="L247"></a><tt class="py-lineno">247</tt> <tt class="py-line"> </tt> <a name="L248"></a><tt class="py-lineno">248</tt> <tt class="py-line"> <tt class="py-comment"># get indices & radii of points</tt> </tt> <a name="L249"></a><tt class="py-lineno">249</tt> <tt class="py-line"><tt class="py-comment"></tt> </tt> <a name="L250"></a><tt class="py-lineno">250</tt> <tt class="py-line"> <tt class="py-comment"># indices is a list of tuples. Each tuple contains the </tt> </tt> <a name="L251"></a><tt class="py-lineno">251</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-comment"># two indices of a point pair within query_radius of </tt> </tt> <a name="L252"></a><tt class="py-lineno">252</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-comment"># each other.</tt> </tt> <a name="L253"></a><tt class="py-lineno">253</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">indices</tt><tt class="py-op">=</tt><tt class="py-name">kdtree</tt><tt class="py-op">.</tt><tt id="link-31" class="py-name" targets="Method Bio.KDTree.KDTree.KDTree.all_get_indices()=Bio.KDTree.KDTree.KDTree-class.html#all_get_indices"><a title="Bio.KDTree.KDTree.KDTree.all_get_indices" class="py-name" href="#" onclick="return doclink('link-31', 'all_get_indices', 'link-31');">all_get_indices</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L254"></a><tt class="py-lineno">254</tt> <tt class="py-line"> <tt class="py-name">radii</tt><tt class="py-op">=</tt><tt class="py-name">kdtree</tt><tt class="py-op">.</tt><tt id="link-32" class="py-name" targets="Method Bio.KDTree.KDTree.KDTree.all_get_radii()=Bio.KDTree.KDTree.KDTree-class.html#all_get_radii"><a title="Bio.KDTree.KDTree.KDTree.all_get_radii" class="py-name" href="#" onclick="return doclink('link-32', 'all_get_radii', 'link-32');">all_get_radii</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L255"></a><tt class="py-lineno">255</tt> <tt class="py-line"> </tt> <a name="L256"></a><tt class="py-lineno">256</tt> <tt class="py-line"> <tt class="py-keyword">print</tt> <tt class="py-string">"Found %i point pairs within radius %f."</tt> <tt class="py-op">%</tt> <tt class="py-op">(</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">indices</tt><tt class="py-op">)</tt><tt class="py-op">,</tt> <tt class="py-name">query_radius</tt><tt class="py-op">)</tt> </tt> <a name="L257"></a><tt class="py-lineno">257</tt> <tt class="py-line"> </tt> <a name="L258"></a><tt class="py-lineno">258</tt> <tt class="py-line"> <tt class="py-comment"># Do 10 individual queries</tt> </tt> <a name="L259"></a><tt class="py-lineno">259</tt> <tt class="py-line"><tt class="py-comment"></tt> </tt> <a name="L260"></a><tt class="py-lineno">260</tt> <tt class="py-line"> <tt class="py-keyword">for</tt> <tt id="link-33" class="py-name"><a title="Bio.PDB.Polypeptide.i" class="py-name" href="#" onclick="return doclink('link-33', 'i', 'link-17');">i</a></tt> <tt class="py-keyword">in</tt> <tt class="py-name">range</tt><tt class="py-op">(</tt><tt class="py-number">0</tt><tt class="py-op">,</tt> <tt class="py-number">10</tt><tt class="py-op">)</tt><tt class="py-op">:</tt> </tt> <a name="L261"></a><tt class="py-lineno">261</tt> <tt class="py-line"> <tt class="py-comment"># pick a random center</tt> </tt> <a name="L262"></a><tt class="py-lineno">262</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">center</tt><tt class="py-op">=</tt><tt class="py-name">random</tt><tt class="py-op">(</tt><tt class="py-name">dim</tt><tt class="py-op">)</tt><tt class="py-op">.</tt><tt class="py-name">astype</tt><tt class="py-op">(</tt><tt class="py-string">"f"</tt><tt class="py-op">)</tt> </tt> <a name="L263"></a><tt class="py-lineno">263</tt> <tt class="py-line"> </tt> <a name="L264"></a><tt class="py-lineno">264</tt> <tt class="py-line"> <tt class="py-comment"># search neighbors</tt> </tt> <a name="L265"></a><tt class="py-lineno">265</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">kdtree</tt><tt class="py-op">.</tt><tt id="link-34" class="py-name" targets="Method Bio.EUtils.DBIdsClient.DBIdsClient.search()=Bio.EUtils.DBIdsClient.DBIdsClient-class.html#search,Method Bio.EUtils.HistoryClient.HistoryClient.search()=Bio.EUtils.HistoryClient.HistoryClient-class.html#search,Method Bio.KDTree.KDTree.KDTree.search()=Bio.KDTree.KDTree.KDTree-class.html#search,Method Bio.PDB.NeighborSearch.NeighborSearch.search()=Bio.PDB.NeighborSearch.NeighborSearch-class.html#search,Method Bio.Prosite.Pattern.Prosite.search()=Bio.Prosite.Pattern.Prosite-class.html#search,Class Method Bio.Restriction.Restriction.AbstractCut.search()=Bio.Restriction.Restriction.AbstractCut-class.html#search,Method Bio.Restriction.Restriction.RestrictionBatch.search()=Bio.Restriction.Restriction.RestrictionBatch-class.html#search,Function Bio.SCOP.search()=Bio.SCOP-module.html#search,Module Bio.builders.Search.search=Bio.builders.Search.search-module.html,Module Bio.formatdefs.search=Bio.formatdefs.search-module.html,Variable Bio.formatdefs.search.search=Bio.formatdefs.search-module.html#search"><a title="Bio.EUtils.DBIdsClient.DBIdsClient.search Bio.EUtils.HistoryClient.HistoryClient.search Bio.KDTree.KDTree.KDTree.search Bio.PDB.NeighborSearch.NeighborSearch.search Bio.Prosite.Pattern.Prosite.search Bio.Restriction.Restriction.AbstractCut.search Bio.Restriction.Restriction.RestrictionBatch.search Bio.SCOP.search Bio.builders.Search.search Bio.formatdefs.search Bio.formatdefs.search.search" class="py-name" href="#" onclick="return doclink('link-34', 'search', 'link-34');">search</a></tt><tt class="py-op">(</tt><tt class="py-name">center</tt><tt class="py-op">,</tt> <tt class="py-name">query_radius</tt><tt class="py-op">)</tt> </tt> <a name="L266"></a><tt class="py-lineno">266</tt> <tt class="py-line"> </tt> <a name="L267"></a><tt class="py-lineno">267</tt> <tt class="py-line"> <tt class="py-comment"># get indices & radii of points</tt> </tt> <a name="L268"></a><tt class="py-lineno">268</tt> <tt class="py-line"><tt class="py-comment"></tt> <tt class="py-name">indices</tt><tt class="py-op">=</tt><tt class="py-name">kdtree</tt><tt class="py-op">.</tt><tt id="link-35" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.get_indices Bio.KDTree.KDTree.KDTree.get_indices" class="py-name" href="#" onclick="return doclink('link-35', 'get_indices', 'link-16');">get_indices</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L269"></a><tt class="py-lineno">269</tt> <tt class="py-line"> <tt class="py-name">radii</tt><tt class="py-op">=</tt><tt class="py-name">kdtree</tt><tt class="py-op">.</tt><tt id="link-36" class="py-name"><a title="Bio.KDTree.CKDTree.KDTree.get_radii Bio.KDTree.KDTree.KDTree.get_radii" class="py-name" href="#" onclick="return doclink('link-36', 'get_radii', 'link-23');">get_radii</a></tt><tt class="py-op">(</tt><tt class="py-op">)</tt> </tt> <a name="L270"></a><tt class="py-lineno">270</tt> <tt class="py-line"> </tt> <a name="L271"></a><tt class="py-lineno">271</tt> <tt class="py-line"> <tt id="link-37" class="py-name" targets="Variable Bio.MarkovModel.x=Bio.MarkovModel-module.html#x,Variable Bio.Statistics.lowess.x=Bio.Statistics.lowess-module.html#x"><a title="Bio.MarkovModel.x Bio.Statistics.lowess.x" class="py-name" href="#" onclick="return doclink('link-37', 'x', 'link-37');">x</a></tt><tt class="py-op">,</tt> <tt class="py-name">y</tt><tt class="py-op">,</tt> <tt class="py-name">z</tt><tt class="py-op">=</tt><tt class="py-name">center</tt> </tt> <a name="L272"></a><tt class="py-lineno">272</tt> <tt class="py-line"> <tt class="py-keyword">print</tt> <tt class="py-string">"Found %i points in radius %f around center (%.2f, %.2f, %.2f)."</tt> <tt class="py-op">%</tt> <tt class="py-op">(</tt><tt class="py-name">len</tt><tt class="py-op">(</tt><tt class="py-name">indices</tt><tt class="py-op">)</tt><tt class="py-op">,</tt> <tt class="py-name">query_radius</tt><tt class="py-op">,</tt> <tt id="link-38" class="py-name"><a title="Bio.MarkovModel.x Bio.Statistics.lowess.x" class="py-name" href="#" onclick="return doclink('link-38', 'x', 'link-37');">x</a></tt><tt class="py-op">,</tt> <tt class="py-name">y</tt><tt class="py-op">,</tt> <tt class="py-name">z</tt><tt class="py-op">)</tt> </tt> <a name="L273"></a><tt class="py-lineno">273</tt> <tt class="py-line"> </tt><script type="text/javascript"> <!-- expandto(location.href); // --> </script> </pre> <br /> <!-- ==================== NAVIGATION BAR ==================== --> <table class="navbar" border="0" width="100%" cellpadding="0" bgcolor="#a0c0ff" cellspacing="0"> <tr valign="middle"> <!-- Tree link --> <th> <a href="module-tree.html">Trees</a> </th> <!-- Index link --> <th> <a href="identifier-index.html">Indices</a> </th> <!-- Help link --> <th> <a href="help.html">Help</a> </th> <th class="navbar" width="100%"></th> </tr> </table> <table border="0" cellpadding="0" cellspacing="0" width="100%%"> <tr> <td align="left" class="footer"> Generated by Epydoc 3.0.1 on Mon Sep 15 09:28:08 2008 </td> <td align="right" class="footer"> <a target="mainFrame" href="http://epydoc.sourceforge.net" >http://epydoc.sourceforge.net</a> </td> </tr> </table> <script type="text/javascript"> <!-- // Private objects are initially displayed (because if // javascript is turned off then we want them to be // visible); but by default, we want to hide them. So hide // them unless we have a cookie that says to show them. checkCookie(); // --> </script> </body> </html>