Reimplement the stitcher

[Donaim]

The existing implementation of stitching has shown to produce nonsensical results in certain cases. The results from stitching should be a logical summation of its parts, but currently, they sometimes are not. The root cause appears to be the reliance on regions of the reference genome, rather than contigs produced by the assembler. And in cases when some regions have low concordance with the reference genome, they are aligned differently, producing conflicting versions of overlaps between them.

Objectives:

1. In scenarios where a single contig has been assembled, stitching should return it as the stitched consensus.
2. When multiple contigs are present, the result of putting them together should not be too surprising.
3. Other parts of the pipeline should not be significantly affected by this change.

Tasks:

• [x] Review the existing stitching code and understand the alleged issues.
• [x] Plan the strategy for the new implementation. This includes determining how to handle single and multiple contig scenarios.
• Implement the stitching algorithm
  • Develop a CIGAR tools library to handle CIGAR strings and coordinate mappings.
    • [x] Create functions for extending, converting, and translating coordinates between query and reference sequences.
    • [x] Implement a CigarHit data class to manage slicing operations, overlaps, and MSA conversions.
    • [x] Add and refine methods for handling insertions, deletions, cuts, and strip operations in the CIGAR context.
    • [x] Resolve any floating point errors and off-by-one issues within the Cigar tools.
    • [x] Ensure that the Cigar tools maintain the associative property during operation combinations.
    • [x] Make the CigarHit class immutable.
    • [x] Remove unused methods to simplify the API.
    • [x] Improve docstrings to aid in the understanding of CIGAR operations and library usage.
  • [x] Implement a proof of concept algorithm that works for simple cases.
  • [x] Streamline context usage in the stitcher.
  • [x] Prevent name collisions for names of temporary contigs.
  • [x] Create a staging area (e.g., main() entry point) to integrate the contig stitcher and test it in an isolated environment before full pipeline integration.
  • [x] Treat cross-alignments as anomalies.
• Implement tools for diagnostics.
  • [x] Develop logic to handle unaligned contig parts to ensure complete contig representation.
  • [x] Refactor contig size calculations to simplify the visualizer interface.
  • [x] Implement visual differentiation in the visualizer for distinct contig sections.
  • [x] Improve visual positioning for smaller images and negative coordinate handling in the visualizer.
  • [x] Colour-code the reference track in the visualizer based on coverage statistics.
  • [x] Debug and correct visual representation for cross-alignments.
  • [x] Fix numbering inconsistencies in the visualizer.
  • [x] Optimize visualizer output for representation of discarded contigs.
  • [x] Resolve the problem where certain contigs are incorrectly discarded when they should be visualized.
  • [x] Investigate cases of duplicated visual representation of discarded unaligned contig parts.
  • [x] Fix the visualizer's handling of unaligned contig parts as violated in test_correct_processing_of_two_overlapping_and_one_separate_contig_2.svg.
  • [x] Ensure that the strand parameter is checked every time an arrow is drawn in the visualizer.
  • [x] Fix HCV landmarks not displaying properly.
  • [ ] #1086
• Integrate the new stitcher into the pipeline.
  • [x] Basic integration into existing denovo path.
  • [x] Make the old contigs.csv file still produce the same output as before the stitcher by introducing a new output file contigs_stitched.csv to be used in downstream analyses.
  • [x] Produce additional original versions of unstitched files, named contigs_unstitched.csv and remap_unstitched_conseq.csv
  • [x] Update proviral pipeline to use the original unstitched files.
• Thoroughly test the new implementation.
  • [x] Add basic scenario-based tests.
  • [x] Add basic property-based tests.
  • [x] Add basic visualizer tests.
  • [x] Validate the handling of cases with reverse complement alignments.
  • [x] Develop and implement targeted tests for visualizer specifically.
  • [ ] Ensure 100% coverage.
• [x] #1089
• [ ] #1087

Notes:

This reimplementation may provide opportunities for simplification in the regions alignment code, which is currently very complex.

[Donaim]

Current version of the algorithm (https://github.com/cfe-lab/MiCall/pull/1032/commits/ea58060b47d625ea47fd571e0487c0d5bee6389b) does work for simple cases.

[Donaim]

Current version of the algorithm (https://github.com/cfe-lab/MiCall/pull/1032/commits/7a153c05a4d1448798039f291b8065c9145a90e7) works on real-world examples, and produces expected results. Now it is about finding and fixing individual bugs.

[Donaim]

Currently working on the diagnostics. It turned out to be useful for finding bugs... Reordering goals.

[Donaim]

Part of the diagnostics is the visualizer (diagram maker) that is based on logs. It turned out to be almost as difficult to implement as the stitcher itself.

The first version is implemented in https://github.com/cfe-lab/MiCall/pull/1032/commits/7e84f61c185a66bcbd37bc091a159f922a3d6fd6

[Donaim]

The task list in the issue description has been updated to better reflect the conceptual progress and milestones we've achieved as documented in our commits. These updates stem directly from our commit history and practical work on the stitcher and its diagnostics.

[Donaim]

The introduction of new stitcher changes contents and handling of some input/output files.

Below is a breakdown:

Same Content

The following table lists files that have identical contents in both the old and new versions. The dash symbol (-) indicates that the contents of the old file may differ from the new file, although they might coincide occasionally.

Old File	New File
g2p_csv	g2p_csv
g2p_summary_csv	g2p_summary_csv
remap_counts_csv	-
remap_conseq_csv	-
unmapped1_fastq	unmapped1_fastq
unmapped2_fastq	unmapped2_fastq
conseq_ins_csv	conseq_ins_csv
failed_csv	failed_csv
cascade_csv	-
nuc_csv	-
amino_csv	-
insertions_csv	-
conseq_csv	unstitched_conseq_csv
conseq_all_csv	-
concordance_csv	-
concordance_seed_csv	-
failed_align_csv	-
coverage_scores_csv	-
coverage_maps_tar	-
aligned_csv	-
g2p_aligned_csv	g2p_aligned_csv
genome_coverage_csv	-
genome_coverage_svg	-
genome_concordance_svg	-
contigs_csv	unstitched_contigs_csv
read_entropy_csv	read_entropy_csv
conseq_region_csv	-
conseq_stitched_csv	-

Same Role

The following table lists files that serve the same purpose in the pipeline across most use cases and within the proviral pipeline specifically:

Old File	Most Usecases	Proviral Pipeline
g2p_csv	g2p_csv
g2p_summary_csv	g2p_summary_csv
remap_counts_csv	remap_counts_csv
remap_conseq_csv	remap_conseq_csv
unmapped1_fastq	unmapped1_fastq
unmapped2_fastq	unmapped2_fastq
conseq_ins_csv	conseq_ins_csv
failed_csv	failed_csv
cascade_csv	cascade_csv	cascade_csv
nuc_csv	nuc_csv
amino_csv	amino_csv
insertions_csv	insertions_csv
conseq_csv	conseq_csv	unstitched_conseq_csv
conseq_all_csv	conseq_all_csv
concordance_csv	concordance_csv
concordance_seed_csv	concordance_seed_csv
failed_align_csv	failed_align_csv
coverage_scores_csv	coverage_scores_csv
coverage_maps_tar	coverage_maps_tar
aligned_csv	aligned_csv
g2p_aligned_csv	g2p_aligned_csv
genome_coverage_csv	genome_coverage_csv
genome_coverage_svg	genome_coverage_svg
genome_concordance_svg	genome_concordance_svg
contigs_csv	contigs_csv	unstitched_contigs_csv
read_entropy_csv	read_entropy_csv
conseq_region_csv	conseq_region_csv
conseq_stitched_csv	conseq_csv