A general technique of building or generating graph from the existing sequence is using the de Bruijn graph. Exploring blocks from various microbial genome sequences has some obstacles as they have less change in their characteristics. The motive is to explore synteny blocks.The genome sequences are closely related. Synteny Block finding which is the undertaking of breaking down genomes into non-covering profoundly rationed portions has turned out to be essential in genome correlation. In this paper, we propose an approach using BWT matrix and FM index to find MUMs by comparing two genomes by ensuring the uniqueness of the MUMs. For example, Needleman and Wunsch (Global alignment) and Smith and Waterman (Local alignment) algorithms. Many significant algorithms are there to align two genomes. That is each MUM can be only once in each genome, as it is unique. It shows the common sub-sequences between two genomes and the sub-sequences must be unique in both the genomes. MUMs are the Maximal Unique Matches between two genomes of different organisms/species. A dynamic programming approach is proposed to solve this problem which will give faster output for lower k-mers. Tuple length k has the impact on the speed of searching, usage of memory and algorithm’s sophistication. We search in the database of query sequences by retriving “hits” for each query sequence’s every k-tuple from the hash table and then find the sorted order of the results. Hash table method is used for the purpose of storing the positions of each k-tuple occurred.
SSAHA (Sequence Search and Alignment by Hashing Algorithm), for performing efficient searching procedure on very large DNA database, sequences are preprocessed by dividing them consecutively in k-tuples of bases. Here three proposed improvements of the existing three approaches is discussed and named as SSAHA for exact or partial match finding in sequences of DNA database, finding MUMmer using BWT and FM index and improvement in the tool Sibelia to find synteny block. String comparison is a key concept applied to determine different properties of DNA or genome. In context of working in the diversified field of computational biology, Finally, an improved version of existing Sibelia tool’s algorithm is proposed to find out synteny blocks from microbial genome, where existing algorithm determines only the loops greater than the size of bulges whereas the proposed algorithm determines loops of all sizes. Then a genome alignment algorithm is described that will find out MUMs (Maximal Unique Match) where Burrows Wheeler Transform matrix and an additional data structure FM (Ferragina and Manzini) index are used instead of suffix tree. At first, a dynamic programming algorithm for small k-mer is described which is based on the existing hash table SSAHA method to search large DNA database that gives better run time for small k-mer.
In this article, three different existing algorithms are described with some additional features, which provide better performance in terms of different performance measures. String comparison algorithms are the pathway to determine various characteristics of genomes, DNA or protein sequences.
0 kommentar(er)
