|
Computing technologies are playing an important role in biology since the launch of Human Genome Project. Parallel computing, acts as an effective way to speed up biological computing. Sequence assembly and sequence alignment are the most computing intensive parts of biological computing. They have benefited immensely from parallel computing.
Sequence assembly is also called as fragment assembly, is used to recover fragments and then build the original sequence. It is an important step in DNA sequencing. Due to large amount of biological data, it takes a very long time to assemble the fragments of a middle-sized genome such as rice. Sequence assembly is used to recover the fragments that are broken fro DNA sequences and assemble them into the original sequences. The most widely sued approach for breaking DNA sequence is whole genome shotgun (WGS), which is less expensive and quicker than other methods. The WGS fragments the genome into many pieces of various sizes. This fragmentation can be done in several ways, such as physically shaking the DNA and cutting it with restriction enzymes.
Biological sequence assembly often costs a lot in computing time even for a small or medium sized genomes because of the large magnitude of iterative computing. But most of the current assemblers are sequential programs. Biological data has to be partitioned before applying these programs to assemble the genome. The partition is conducted according to similarities. This process is not accurate. So errors could be introduced by the participation. These errors can be corrected by the assemblers.
A parallel Euler sequence assembly approach is used for the process. This method stores all the genomic data in the form of distributed hash table so as to assemble this data as a whole. This eliminates the errors incurred by approximately partitioning the fragments into groups and assembling them into groups, as in other approaches. The main contribution of the Euler assembly approach is that it transforms the biological sequence assembly problem into an Euler path problem that has a polynomial solution, which is a solution to the notorious “repeat” problem.
In the Euler sequence assembly approach, tuples are the minimal units to be assessed, rather than the reads as in other approaches. Tuples are generated from reads. Tuples from one read are all the substrings of that read with the same length, which are normally 20. All the tuples generated from a debruijn graph. The vertices of the graph are the tuples. Supposing the length of a tuple is l, if the last l -1 nucleotide acids of one tuple are the same as the first l-1 nucleotide acid of another tuple, there will be a directed edge in the graph which connects these two adjacent tuples. The Euler assembly approach is to find all the Euler paths in the graph. Each path is in fact a contig. The core of the Euler approach is consistency analysis rule which solves the problems of path selection for branches when looking for Euler paths in a graph.
Although Euler sequence assembly algorithm has a lower computing complexity than other approaches, it still needs a lot of time to assemble those biological fragments for small or middle sized genomes. Parallel computing is an efficient way to solve computing intensive problems, and sequence assembly has shown good parallelism that can be exploited. Fact, parallel computing has been used in the current sequence assembly, for example, in sequencing the genome of the human being in the Human Genome Project. Many computing nodes have participated in the process of assembling fragments from the human genome. But this can not be called as “real” parallel computing for sequence assembly because, in this approach, all fragments have to be first partitioned into many groups whose size is suitable for assembling in a single computing node. Fragments from one group can be assembled only with other fragments within the same group. So, each computing node can assemble the fragment within the same group. So, each computing node can assemble the fragment only from perspective of a group, and not the whole genome. The partition of the fragments is conducted sequentially and may produce errors. These errors will result in incorrect sequence assembly because the assembly is confined to individual groups and can not cross these groups.
|
