Fast Approximate Search in Strings with Rearrangements
One of the types ofgenovariation is the intrcoequence rearrangement. If we consider nucleotide sequence 03 a string, then the intrasequence rearrangement may be interpreted as mutual transposition of string parts.Common instruments for the analysis of the nucleotide strings (such as BLAST 1) are based on the computation of edit distance. Edit-distance approach is very efficient in case of such mutations as deletion, insertion or substitution of a single nucleotide, but almost inapplicable for the sequences with rearrangements.Another approach to the approximate searching in strings under condition of sequence rearrangements is Block-edit approach 2, However algorithms based on this approach have a very high time complexity, which leads to the tight restrictions in its bioinformatics applications.One of the modern methods of approximate searching with rearrangements is reflected in QUASAR system 7. In this article an approach to the search is proposed that is similar to QUASAR. The proposed approach gives visualization of the searching results. As distinct from QUASAR the proposed approach does not involve edit distance concept which allows to obtain time complexity O(n·ln m),where n is the length of data string and m is the length of pattern. Another peculiarity is the visualization of the results.
approximate search intrasequence rearrangements bioinformatics.
Evgeny Ivanko
Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences
国际会议
Firth IEEE International Conference on Cognitive Informatics(第五届认知信息国际会议)
北京
英文
845-849
2006-07-17（万方平台首次上网日期，不代表论文的发表时间）