A simple heuristic for a binary tree of depth b can be implemented on {0,1}b. The binary barcode of a node can determine its depth in the tree: the location of the first ‘1’ in the barcode (first from the left) defines the depth. For instance, in a tree of total depth 4, 0001 is the root of the tree, and 0100 occurs at depth 3 (Fig. S4a). The heuristic consists of a buffer of identities, initialized with the root node. At each step, a barcode is removed from the buffer. A new rule is introduced by using the current barcode as the source set, while the destination set requires removing the first bit of the barcode and adding an X to the end. Then, the two new nodes that are invoked in the destination set are added to the buffer. This process repeats until the destination nodes are selected from the terminal depth (ID starts with ‘1’), at which point the destination nodes are not added to the buffer.

To illustrate, let us again consider a tree with depth b = 4. At initialization, the buffer consists of only the root node, 0001 (Fig. S1a, top). We introduce a rule with source set 0001. The destination set is created by dropping the first ‘0’ from the source node, and adding an ‘X’ at the end: 001X. This results in the rule (0001)O(001X). We then add the two nodes in the destination set to the buffer, which now consists of 0010 and 0011. These will then lead to two new rules: (0010)O(010X) and (0110)O(011X). After introducing these new rules the buffer will consist of 0100, 0101, 0110, and 0111. This will lead to the third set of rules: (0100)O(100X), (0101)O(101X), (0110)O(110X), and (0111)O(111X). However, this step will not place new barcodes in the buffer, as we have reached the final depth (there is 1 as the first bit). Thus, once these rules have been introduced the buffer is empty and the resulting binary tree is now complete (Fig. S4a).

注意:以上内容是从某篇研究文章中自动提取的,可能无法正确显示。



Q&A
请登录并在线提交您的问题
您的问题将发布在Bio-101网站上。我们会将您的问题发送给本研究方案的作者和具有相关研究经验的Bio-protocol成员。我们将通过您的Bio-protocol帐户绑定邮箱进行消息通知。