Microsoft Acquires 10 Million Strands Of DNA For Digital Storage Experiment

Microsoft Acquires 10 Million Strands Of DNA For Digital Storage Experiment: Microsoft is buying 10 million strands of DNA from startup Twist Bioscience, a company that makes storage-ready synthetic DNA. Microsoft will be using the DNA strands in experiments pertaining to data storage.

Microsoft uses synthetic DNA

https://plus.google.com/+Engadget/posts/cNd2qwqiaT7?_utm_source=1-2-2

From DNA to Proteins

New Letters Added to the Genetic Alphabet

New Letters Added to the Genetic Alphabet

Finding shortest or most optimum route between two points with inchrosil

A typical problem of graph theory is to find the shortest or most optimal route from an initial point to an end point. The approach presented to this problem is to consider a directed graph, weighted (positive or negative) and using the characteristics of the DNA, by Inchrosil technology. In this way, using a device based on Inchrosil, it is possible to find the shortest or most optimal path. Let us give an example, supposing that we want to resolve the problem of Figure 1 by the lists of adjacencies and set theory.

Figure 1: Graph Example

In the graph of Figure 1, it is possible to represent as a list of adjacencies, where the nomenclature would be the following; (source vertex, edge, destination vertex), therefore, the graph would remain as follows.

• Node(s): {(s,x1,u),(s,x2,v)}
• Node(u): {(u,x3,w),(u,x7,v)}
• Node(v) : {(v,x5,t)}
• Node(w): {(w,x4,v),(w,x6,t)}

It should be highlighted that, in graph theory, the data structure, list of adjacencies, is defined as a structure which permits associating a list which contains all those vertices j, which are adjacent thereto, to each vertex i. In this way, space is saved in its representation and, in addition, the graph can be represented by a vector of n components (if |V|=n), where each component is going to be a list of adjacency corresponding to each one of the vertices of the graph. Furthermore, each element of the list consists of a field indicating the adjacent vertex. On the other hand, if the graph was labelled, it would be necessary to add a second field to show the value of the label.

Using set theory, we can form a set with all elements of the adjacency list, i.e. the elements (vertex, edge, vertex). This set that we have formed would have premises which are enumerated below.

• If there are two elements belonging to the set, such as e1 and e2, it is observed that the end component of e1 is equal to the initial component of e2; both elements react, creating a new element, which will belong to the set.
• If there are elements which belong to the set, which contain components which are initial and final, they do not react with the rest, since they would now be solution.
• Two elements that react have a positive ratio or 1; instead two elements which do not react have a negative ratio or 0.
• The elements with initial components and that belong to the adjacency lists, once reacted do not react again.

If it is known that E is the set of elements and C is the set of components, we can see that the reaction is the following operation:

In this case, we have a set of elements belonging to the adjacencies lists, which we will denote as Element-[i], therefore, the set would initially remain in the following form.

• Element-1: {(s, x1, u)}
• Element-2: {(s, x2, v)}
• Element-3: {(u, x3, w)}
• Element-4: {(u, x7, v)}
• Element-5: {(w, x4, v)}
• Element-6: {(w, x6, t)}
• Element-7: {(v, x5, t)}

With this initial set, its elements can be analysed and it can be seen how these premises associated to the set can be fulfilled and new elements be created. In this case, it can be seen that Element-1 would react with Element-3 and Element-4, forming Element-8 and Element-9, respectively. It can also be seen that Element-2 reacts with Element-7 to form Element-10, which is now solution. After this, the set would remain as follows.

• Element-1: {(s, x1, u)} [does not react] premise 4
• Element-2: {(s, x2, v)} [does not react] premise 4
• Element-3: {(u, x3, w)}
• Element-4: {(u, x7, v)}
• Element-5: {(w, x4, v)}
• Element-6: {(w, x6, t)}
• Element-7: {(v, x5, t)}
• Element-8: {(s, x1, u, x3, w)}
• Element-9: {(s, x1, u, x7, v)}
• Element-10: {(s, x2, v, x5, t)}

In a following round, it is observed that Element-8 can react with Element-5 forming Element-11 and, that also Element-8 can react with Element-6 to form Element-12, finally, Element-9 reacts with Element-7 forming Element-13. In this round the set would be as follows.

• Element-1: {(s, x1, u)} [does not react] premise 4
• Element-2: {(s, x2, v)} [does not react] premise 4
• Element-3: {(u, x3, w)}
• Element-4: {(u, x7, v)}
• Element-5: {(w, x4, v)}
• Element-6: {(w, x6, t)}
• Element-7: {(v, x5, t)}
• Element-8: {(s, x1, u, x3, w)}
• Element-9: {(s, x1, u, x7, v)}
• Element-10: {(s, x2, v, x5, t)}
• Element-11: {(s, x1, u, x3, w, x4, v)}
• Element-12: {(s, x1, u, x3, w, x6, t)}
• Element-13: {(s, x1, u, x7, v, x5, t)}

Observing the set, it is seen that there is a single reaction, that of Element-11, which reacts with Element-7 to form Element-14. With this last reason, the set would be as follows.

• Element-1: {(s, x1, u)} [does not react] premise 4
• Element-2: {(s, x2, v)} [does not react] premise 4
• Element-3: {(u, x3, w)}
• Element-4: {(u, x7, v)}
• Element-5: {(w, x4, v)}
• Element-6: {(w, x6, t)}
• Element-7: {(v, x5, t)}
• Element-8: {(s, x1, u, x3, w)}
• Element-9: {(s, x1, u, x7, v)}
• Element-10: {(s, x2, v, x5, t)}
• Element-11: {(s, x1, u, x3, w, x4, v)}
• Element-12: {(s, x1, u, x3, w, x6, t)}
• Element-13: {(s, x1, u, x7, v, x5, t)}
• Element-14: {(s, x1, u, x3, w, x4, v, x5, t)}

It can be seen that the results are Element-10, Element-12, Element-13 and finally Element-14, since they have initial and final components. The operation of this previous approach, to find the solutions or paths, is performed sequentially. But in the circuit is performed in parallel form, i.e. the circuit has considered two sets; the first set C1, is formed by the elements which contain initial components and the elements that do not contain final components. The second set C2 is formed by the elements that contain final components and the elements which do not contain initial components. Both sets are encoded by Cod-Inchrosil and, stored in different strands Figure 2-10, respectively. These strands link their components by a circuiting which contains comparers Figure 2-9, forming a matrix as observed in Figure 2; in this way, they react in parallel form, obtaining a set of reactions encoded as positive (1) or negative (0). These reactions form a matrix of 0s and 1s. Therefore, there are two sets C1 and C2, which represent the two aforementioned sets and which are encoded in Inchrosil strands. On the other hand, we have a Cr, which is formed by the reactions between the elements of set C1 and C2; in this way, the reaction is redefined as the operation, where e2C2 and e1C1, then e1e2Cr, with being the reaction and the values it may take are 0 or 1. As is observed, a new element is not created in the reaction which must react, but all react at the same time and it is indicated in a matrix, with a 1 if there had been a reaction or the reaction is positive and, in contrast, with a zero if there had not been a reaction or the reaction has been negative.

Figure 2: Circuit to solve short path

Once the matrix has been obtained with the reactions of all elements with all others, this information is passed to a buffer and, by software or circuitry, path recovery algorithms are applied to it, which do not have a very high cost and are of polynomial order. If weighted graphs are considered, the weights would be stored in a memory (Inchrosil memory or another type of memory), therefore, the edges of the previous graph contain the direction and not the value of the weight, the motive why large quantities can be used for the weights and the directions have a determined length. Once the edges of the path have been found, it is only necessary to add the costs of each edge, to obtain the total cost of the path. Then with the total costs, the paths can be sorted according to sorting criteria; all of this can be performed by circuitry or software modules, which would be connected with the device. This circuit resolves the problems posed in Dijkstra's, Floyd-Warshall and Bellman-Ford's and Ford-Fulkenson's algorithms, as they can consider negative costs, etc.

The advantage of these systems is the easy incorporation in existing hardware systems, since both are based on electronics and integrated circuits. On the other hand, it is a hardware alternative for the existing calculation systems, since with the software systems they need another environment (operating system, virtual machines, etc.) to function and, instead, this device would be connected directly to the circuitry of the host device.

Resolving Eulerian path with inchrosil

Eulerian paths could define as graph which visits every edge exactly once, with singularity starts and ends on the same vertex. Therefore, an Eulerian path is a cycle which contains all edges of a graph just once. This problem was posed and resolved by Leonhard Euler himself in 1736 in a problem which has the name of the seven bridges of the city of Königsberg. The problem is enunciated in the following form: two islands in the Pregel River, in Königsberg are joined together and with land by seven bridges.

• Is it possible to take a walk starting by any of the four parts of land, crossing each one of the bridges just once?

Euler approached the problem representing each part of land by one point and each bridge by a line, joining the corresponding dots. Then, the previous problem can be transferred to the following question:

• Is it possible to travel round the representation without repeating the lines?

Euler demonstrated that it was not possible because the number of lines that affect each dot is uneven (a necessary condition to be able to enter and exit each dot). Therefore, this problem posed questions such as the following;

• How is it possible to cover the cable of this electricity grid without repeating sections of grid?
• How can this route be performed, passing through specific streets?

There is a complexity to solve these cycles’ problems, by this reason, we have considered inversely, i.e. all vertices could be converted in edges and all edges could be converted in vertices, with simple conversion, we can calculate any Hamiltonian path associated of conversion. On the other hand, since now the vertices represent the edges and it is necessary to know what sequence of vertices we should follow to be able to pass through all the edges.

Let us suppose the directed and non-weighted graph of Figure 1, which would be a multi-graph, i.e. a non-deterministic automaton.

Figure 1: Eulerian path.

The graph of Figure 8 can also be represented as follows, where V₁ is the set of vertices and E₁ is the set of edges.

G₁=(V₁,E₃) with V₁=(v₁,v₂,v₃) and E₁=(a₁,a₂,a₃,a₄,a₅,a₆)

Furthermore, we have the following vertex links, by means of edges;

U={(v₁,v₂,a₁),(v₁,v₂,a₂),(v₁,v₂,a₃),(v₂,v₃,a₄),(v₂,v₃,a₅),(v₂,v₃,a₆),(v₃,v₁,a₆)}

Where the nomenclature used for these links is (source vertex, destination vertex, edge). If said inversion is made, and if the edges are considered as vertices and the vertices as edges, we would obtain the following graph.

G₂=(V₂,E₂) with V₂=(a₁,a₂,a₃,a₄,a₅,a₆) and E₂=((v₁,v₂),(v₂,v₃),(v₃,v₁))

Furthermore, we have the following vertex links, by means of edges;

W= {(a₁, v1, v2, v2, v3, a4) . . .}

Therefore, the graph will have the form shown in Figure 1. Consequently, if the Hamiltonian path of the previous graph G₂ is shown, it can be stated that there is a solution or Eulerian path G₁. It can also be considered that the graph is weighted, the total costs of each one of the paths can be calculated and, therefore, sorted by cost, although the Eulerian paths do not have weight, new problems of optimization in the Eulerian paths could be posed. In conclusion, if a Hamiltonian path exists in graph G₂, it can be stated that there is an Eulerian path in graph G₁. Finally, it can be stated that Eulerian cycles can be resolved, for which purpose, when encoding the base of strands or banks of strands, it was established that the initial node was the same as the final. In this way, cycle problems can be resolved using the Hamiltonian Path device.

Resolving Travelling Salesman Problem with Inchrosil

The travelling salesman problem (TSP) is one of the most famous and best studied in the computational area, being one the most difficult to resolve, due its complexity, which is considered a NP-complete problem. In the previous section, we have described an electronic system to solve Hamiltonian path problem with a cost approximately of polynomial order, in this paragraph, the graph to analyze has a weighted and direction in its paths, where only one or set Hamiltonian paths are solution of TSP, so first step would be found all Hamiltonian paths at the graph, and next steps would be calculated final cost each Hamiltonian path found, using its weighted and directions, by this reason, in our research, we have used the same infrastructure explained in Hamiltonian Path device, which would obtain all Hamiltonian paths, later with these paths, the system would calculate each individual cost and compare all cost to get which is the best Hamiltonian path, always depending a initial characteristics established by programmer/user.

All these calculations could be done in parallel, also all criteria to sort path cost could be stored in different modules of the system, in this way any operation is quick and faster to do. In this article, we have considered two different systems to do all mathematical operation and choice the best Hamiltonian path cost, depending one specific criteria. The first system contains software to calculate and storage all paths cost, which determinates the correspondence between weight-edge. This system, once the individual cost is obtained, calculates the total cost of each path. When all cost is calculated, the system order all cost by one specific criterion (for example, from least to greatest, from greatest to least, etc).

Finally, system has a set of ordered paths and the system can choose the best path. In Figure 1 shows first system to calculate TSP, the reference Figure 1-21 in figure represents the circuit to obtain the Hamiltonian path, Figure 1-22 the connection interface with interface Figure 1-25 of a data processing module Figure 1-23, reference Figure 1-24 is a database and Figure 1-26 a cost and sorting calculation module. The reference Figure 1-27 represents an external data request device.

Figure 1: First System to calculate any TSP.

On the other hand, the intermediate data was stored in the database, i.e. the weights of the edges, etc. being these systems as support to the calculations, which are going to be made or are have been made.

At second system (system shown in Figure 2) uses memories to store and manipulate all weight of vertex-edge. These memories could be an electronics circuit using Inchrosil technology or other kind of memories. In this case, system does not store real value of weight at the edge, only a reference of memory address (point reference), because the value can be huge and any system address has an established size, by this reason, it is better to store only memory address, later with this memory address, system can access real value stored.

On the other hand, this second system follows next steps: when the Hamiltonian paths are determined, by the circuit Figure 2-21, it seeks the value of the edges in the memory Figure 2-28, since as we know its address, we will know its value. These costs are added and will be looked for by circuitry mediation, i.e. a bus Figure 2-32 and adders Figure 2-30, on the other hand, to obtain the total cost of each path which can be stored in the memory Figure 2-28 with consecutive addresses. As in the previous implementation, the user or the system which receives this information as input chooses with which path it remains, by criteria of choice, outside the devices described in this article. In this example, reference Figure 2-22 represents the connection interface with an interface Figure 2-25a of the data processing module Figure 2-23a, reference Figure 2-29 the sorting module, Figure 2-31 a connection interface of module Figure 2-23a with a data fetching device Figure 2-27.

Figure 2: Second system to calculate any TSP.