Study On Biosequence Comparison And Motif Finding Algorithms

Being one of the academic areas that develop rapidly, Bioinformatics uses knowledge in computer science to solve biology problems concerning DNA, protein etc. Bio-sequence comparison and motif finding are fundamental problems in bioinformatics, and play key roles in bio-system revolution, gene regulation, disease remedy, and viral origins field.With the development of DNA sequencing technique, bio-sequence data has increased so rapidly that can't be analysed only by handwork. On the other hand, the rapid development of computer and network technology has equipped molecular biologist with novel powerful methods to deal with bio-sequence. This paper mainly focuses on the problem of bio-sequence comparison and motif finding. The main content in the paper are described below:(1) Study on motif finding in DNA sequencesDNA sequence is one of the most frequent sorts of bio-sequence data. There are two kinds of method to detect motif in a group of DNA sequences, statistical and combinatorial. A popular motif finding model, FM model is studied. Firstly, based on sample sequence comparison we present a novel method to generate feasible motif candidates; then we propose a novel exact motif finding algorithm based on the sampling driven algorithm. Our algorithm has the same sensitive as the pattern driven algorithm but costs less searching time and space. Experiment shows that is better than MITRA, the fatest exact algorithm for the moment.(2) Study on bio-sequence computing in nanocomputing platformBio-sequence computing involves a huge amount of computation in which parallel computing is indispensable. However the problem itself is sequential and hard to be parallelized. Former studies have shown that a new nanocomputing model, Cell Matrix, can solve the problem. Its homogenous and two-dimensional structure ensures manufacturing and scalability. We present a new implemention for a pairwise sequence alignment algorithm so that it can output alignments, and design a motif finding algorithm based on the Cell Matrix model. Finally, we give their computational complexities in term of the cell numbers and cell delays.(3) Study on parallel algorithms for genome sequences reversal sortingGenome sequence reversal is a most common form of genome rearrangement. By studying current sequential algorithms, this paper presents two parallel algorithms with O(lg~2n) and O(lgn) time complexities for computing reversal distance of signed permutation and a linear time parallel algorithm for reversal sorting.(4) Study on genome sequences reversal median problem...