EXHAUSTIVE SEARCH OF HOMOLOGOUS REGIONS BETWEEN TWO LARGE DNA SEQUENCES USING AN ENTROPY MEASURE

This paper presents a time and space efficient algorithm that searches for all homologous regions between two DNA sequences. A homologous region is defined by exact match segments interspersed with poorly matched segments (gaps) that contain high amount of errors. This definition is subject to two input parameters to the algorithm: the minimum length of exact match segments and the maximum length of gaps. We believe that the distribution of the exact match segments in a homologous region reveals more about the quality of homology than the error rate measure based on base-to-base substitution, deletion, and insertion errors.