Distance maps using multiple alignment consensus construction

A method for de novo genetic map assembly of a biomolecule with a plurality of fragment maps corresponding thereto, comprising:

• (a) receiving, at a processor, data representing the plurality of fragment maps;
• (b) performing, with the processor, a multiple map alignment on a defined bundle to determine consensus events and corresponding locations, wherein the defined bundle includes a subset of the plurality of fragment maps;
• (c) monitoring, with the processor, an overhang state of each fragment map in the bundle relative to the consensus events and a bundle size state representing the number of fragments in the defined bundle, whereby a fragment map is removed from the bundle when the corresponding overhang state reaches a predetermined criteria, and when the bundle size state is below a predetermined threshold:
• (d) aligning, with the processor, one or more of remaining fragment maps of the plurality of fragment maps, the remaining fragment maps having a signature, with the consensus events to generate a consensus alignment score;
• and
• (e) aligning, with the processor, the one or more remaining fragment maps to each of the fragment maps in the bundle to generate a corresponding pairwise alignment score;
• and
• (f) adding the one or more remaining fragment maps to the bundle if the consensus alignment score and the pairwise alignment scores exceed a significance threshold.

A non-transitory computer readable medium containing computer-executable instructions that when executed cause one or more computer devices to perform a method for de novo genetic map assembly of a biomolecule with a plurality of fragment maps corresponding thereto, comprising:

• (a) performing a multiple map alignment on a defined bundle to determine consensus events and corresponding locations, wherein the defined bundle includes a subset of the plurality of fragment maps;
• (b) removing one of the number of fragment maps from the bundle when there is no overhang from the consensus events;
• and when the subset of fragment maps in the bundle is less than a predetermined threshold:
• (i) aligning one or more of remaining fragment maps of the plurality of fragment maps, the remaining fragment maps having a signature, with the consensus events to generate a consensus alignment score;
• and
• (ii) aligning the one or more remaining fragment maps to each of the fragment maps in the bundle to generate a corresponding pairwise alignment score, wherein if the consensus alignment score and the pairwise alignment scores exceed a significance threshold the one or more remaining fragment maps are added to the bundle.

A method for performing multiple alignment of a plurality of fragment maps, comprising:

• (a) performing pairwise alignments between each of the fragment maps to generate a graph having a plurality of edges and vertices representing each pairwise relation, wherein each vertex of the graph corresponds to an event on one of the maps, and wherein each edge of the graph corresponds to predicted homologous events;
• (b) generating at least a first ordered set of sets of events representing a multiple alignment reflecting all pairwise alignments by:
• (i) randomly selecting an edge;
• and
• (ii) removing the selected edge and combining its vertices while retaining all other edges if the vertices of the selected edge correspond to different fragment maps;
• (iii) repeating the steps of randomly selecting and removing until either only two vertices remain or no further edges can be removed;