Bioinformatics data processing systems

Abstract

Disclosed is a computer-implemented method of determining at least one optimal alignment of at least part of a first map to at least part of a second map or a plurality of second maps, wherein the maps are physical genome maps and / or restriction maps. The method comprises: receiving first map data indicative of a first ordered list of distances between features of the first map, receiving second map data indicative of a second ordered list of distances between features of the second map or second maps; generating, from the second map data, seed data indicative of a plurality of seeds, each seed comprising at least one of the distances in the second ordered list, wherein the features are restriction sites and distances are fragment sizes. The said method further comprises generating a plurality of candidate alignments from the seed data by searching at least part of the first ordered list to find at least approximate matches for respective seeds, and extending the approximate matches bydynamic programming; determining respective alignment scores for respective candidate alignments; and selecting one or more of the candidate alignments as an optimal alignment or optimal alignments,based on the alignment scores.

Description

field of invention [0001] The present invention relates generally to methods and systems for map comparisons, particularly map-to-sequence (map-to-sequence) alignments, and more particularly to methods and systems for determining the relationship between at least a portion of a first map (e.g., a first physical genome map) and Methods and systems for at least one optimal alignment of at least a portion of a second profile or multiple second profiles (eg, a second physical genomic profile). Background of the invention [0002] Resolving complex repeat structures and rearrangements in the assembly and analysis of large eukaryotic genomes typically resorts to a combination of high-throughput sequencing and genome mapping techniques (eg, optical restriction mapping). Specifically, mapping techniques are able to generate sparse maps of large DNA fragments (150 kilobase pairs (kbp) to 2 Mbp) and thus provide a unique source of information for distinguishing complex rearrangements ...

AI Technical Summary

Problems solved by technology

However, since maps represent ordered lists of continuous values, this extension is not straightforward, especially when considering multiple sources of map drawing errors and their high error rates (Muggli MD. et al., Efficient Indexed Alignment of Contigs to Optical Maps, In Algorithms in Bioinformatics (WABI 2014), LNCS Volume 8701, Wroclaw (Wroclaw, Poland: Springer; 2014p.68-81)

Also, since error rates can vary across technologies, and even across different runs on the same instrument, it is not clear that a generally sensitive map-to-sequence aligner is feasible

Images