## 3 Algorithms
### Modification of the Basic Algorithm  
There are two kinds of cycles that cause trouble: cycles that are connected to a start node, and disconnected cycles. In both cases, there might be sets of nodes that are created like attachments to nodes of the cycle, but do not belong to them, and are not detected by Algorithm 1. In the case of disconnected cycles, we would need to take any node as a start node, which can require some trial and error since a randomly selected node could be attached to the cycle but not necessarily in the cycle itself. However, disconnected cycles in real life DNA fragment sequencing problems are rare, and when they appear, they are usually very small, two or three nodes, that lead to _contigs_ that are too small and that would have been discarded anyway.  
A cycle connected to a start node of the graph appears when there are nodes for which, even when paths that go from a start node to another node \(u\) in the cycle, the value of _d\({}_{in}\)(u)_ never goes to zero because at least one edge comes from the cycle. When Algorithm 1 is done, we can take one of the nodes that went through Step 2.2.1, but that remained with a final value of _d\({}_{in}\)(u) \(>\) 0_, and insert it into the stack to continue with Step 2 of the algorithm. It is necessary, however, to mark those nodes so that they will not be considered again and to avoid the cycle being traversed more than once. The total distance from a start node to the last processed node in the cycle is the sum of the distance from a start point to the cycle entry point plus the length of the cycle, minus the edge that would close the cycle on the start node in the cycle. So we have that if the selected node is \(s\), the previous node in the cycle is \(t\), and the total length of the cycle is \(C\) then:  
\[d(t)=d(s)+C-w(t,s) \tag{5}\]  
Among the distinct entry nodes to the cycle, we could select one with the longest distance to a start node. However, it does not guarantee that we will always find the longest distance to node \(t\) since the value of _w(t, s)_ changes with the selection of \(s\) and there could be another cycle entry node with a smaller value of _d(s)_ but with a small enough value of _w(t, s)_ to give a longest distance. In the case of the DNA fragment assembly problem the values of _w( )_ are in a very narrow range, most of the distances to the start node are big and it is uncommon for them to be similar, so that if our heuristic consists of selecting an s with the longest distance to the start point, we will have a high probability of finding the maximum distance. The modified algorithm (Algorithm 5) is as follows:  
```
1. For each vertex \(v\in S\) with \(d_{in}\)(\(v\)) = 0  1.1. push(Q,v)  1.2. d(v):=0  1.3. origin(v):=v
2. While there are vertices \(v\) with \(d_{in}\)(\(v\)) > 0  2.1. While \(Q\) is not empty  2.1.1. \(u\):=pop(Q)  2.1.2. For every vertex \(v\) where \((u,v)\in E\) and \(v\) is not marked  2.1.2.1.\(d_{in}\)(v):=\(d_{in}\)(v)-1  2.1.2.2.If \(d_{in}\)(\(v\))=0  2.1.2.2.1. \(push(Q,v)\)  2.1.2.2.2. \(d(v):=\max\limits_{(x,v)\in E}\bigl{(}d(x)+w(x,v)\bigr{)}\)  2.1.2.2.3. insert \(d\)(\(v\)) in a heap  2.1.2.2.4. \(father(v)\):=x  2.1.2.2.5. origin(v):=origin(x)
2.2. If the heap is not empty  2.2.1. extract the node \(v\) from heap  2.2.1.1. If \(d_{in}\)(\(v\))>0  2.2.1.1.1. Make \(d_{in}\)(\(v\))=0  2.2.1.1.2. Insert \(v\) in the stack  2.2.1.1.3. Mark the node \(v\)  2.2.1.1.4. Go to step 2.1
```  
**Algorithm 5**Modified maximum distance algorithm  
Notice that Step 2.2.1.1 is required since node \(v\) could have gone through Step 2.1.1 and already be in a path. In this case, we can use the heap to keep the time complexity of the algorithm linear.