2009 | OriginalPaper | Buchkapitel
BAC Overlap Identification Based on Bit-Vectors
verfasst von : Jens-Uwe Krause, Jürgen Kleffe
Erschienen in: Bio-Inspired Systems: Computational and Ambient Intelligence
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
There is no software that accurately calculates the overlap of two BACs fast enough for application to thousands of cases in turn. The problems include unacceptably low speed of dynamic programming algorithms for sequences of the considered size and failure of the faster local alignment methods to identify complete sequence overlaps. Lower sequence quality at both BAC ends and internal difference blocks, being small enough to not significantly increase relative error rates but large enough to terminate local alignments, cause output of multiple overlapping local matches which do not extend to both sequence ends. Based on Myers’ bit-vector algorithm for fast edit distance calculation, we developed the program BACOLAP, that identifies overlapping BACs just as sensitive as global dynamic programming alignment and as fast as local heuristic alignment.