Jv
J. van Bemmelen
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
5 records found
1
Accurately reconstructing viral haplotypes from mixed sequencing samples is crucial for tracking viral evolution, detecting new clinically relevant variants, and guiding effective treatments. Existing de novo haplotype-aware genome assembly methods typically rely on heuristic path extraction strategies, which limit exploration of the full solution space and may fail to recover low-abundance haplotypes. In this work, we investigate the use of an Integer Linear Programming (ILP) formulation for the Minimum Flow Decomposition (MFD) based problem to reconstruct haplotypes and estimate their abundances through a contig variation graph. Our approach integrates three main components: (1) a new pipeline for constructing contig variation graphs from reads and contigs build from these reads, (2) a Minimum Path Cover (MPC) step to estimate the number of haplotypes, and (3) an MFD-based ILP to infer haplotypes and their abundances, with additional strategies to restrict the set of allowed path weights for improved tractability. We evaluate the method on simulated hepatitis C virus (HCV) and HIV datasets, comparing its assembly quality, abundance estimation accuracy, and tractability against Virus-VG and VG-flow. Results show that for low-haplotype, well-structured graphs, the MFD approach matches or exceeds the performance of existing haplotype-aware methods, with notable advantages on HIV data. However, the runtime grows exponentially with the number of haplotypes, which limits its applicability to low haplotype-count samples. Weight-restriction strategies and improving graph construction can mitigate this runtime challenge. Our findings demonstrate both the potential and current scalability limits of MFD-based assembly.
...
Accurately reconstructing viral haplotypes from mixed sequencing samples is crucial for tracking viral evolution, detecting new clinically relevant variants, and guiding effective treatments. Existing de novo haplotype-aware genome assembly methods typically rely on heuristic path extraction strategies, which limit exploration of the full solution space and may fail to recover low-abundance haplotypes. In this work, we investigate the use of an Integer Linear Programming (ILP) formulation for the Minimum Flow Decomposition (MFD) based problem to reconstruct haplotypes and estimate their abundances through a contig variation graph. Our approach integrates three main components: (1) a new pipeline for constructing contig variation graphs from reads and contigs build from these reads, (2) a Minimum Path Cover (MPC) step to estimate the number of haplotypes, and (3) an MFD-based ILP to infer haplotypes and their abundances, with additional strategies to restrict the set of allowed path weights for improved tractability. We evaluate the method on simulated hepatitis C virus (HCV) and HIV datasets, comparing its assembly quality, abundance estimation accuracy, and tractability against Virus-VG and VG-flow. Results show that for low-haplotype, well-structured graphs, the MFD approach matches or exceeds the performance of existing haplotype-aware methods, with notable advantages on HIV data. However, the runtime grows exponentially with the number of haplotypes, which limits its applicability to low haplotype-count samples. Weight-restriction strategies and improving graph construction can mitigate this runtime challenge. Our findings demonstrate both the potential and current scalability limits of MFD-based assembly.
Abundance estimation with the use of environmental samples has been used during the SARS-CoV-2 pandemic to identify the abundances of different lineages. AmpliDiff, an algorithm that tries to find parts of DNA that can differentiate between different input genomes was used on a SARS-CoV-2 dataset to find these amplicons. The AmpliDiff algorithm was able to run on the SARS-CoV-2 set but seemed infeasible for datasets that contain larger or more complex genomes because of the computational requirements and runtime. We introduce a new pre-processing strategy based on selecting the most differentiable coding regions and show the modifications done to AmpliDiff to make AmpliDiff work following this new method. Based on the results we conclude that the approach is promising but still requires more research to be used optimally.
...
Abundance estimation with the use of environmental samples has been used during the SARS-CoV-2 pandemic to identify the abundances of different lineages. AmpliDiff, an algorithm that tries to find parts of DNA that can differentiate between different input genomes was used on a SARS-CoV-2 dataset to find these amplicons. The AmpliDiff algorithm was able to run on the SARS-CoV-2 set but seemed infeasible for datasets that contain larger or more complex genomes because of the computational requirements and runtime. We introduce a new pre-processing strategy based on selecting the most differentiable coding regions and show the modifications done to AmpliDiff to make AmpliDiff work following this new method. Based on the results we conclude that the approach is promising but still requires more research to be used optimally.
Heuristic-Based Primer Set Minimization for PCR
Adaptation of Iterated Local Search for a Set Cover Variant
AmpliDiff is an algorithm for studying environmental samples. As the study of those DNA samples is complicated, the runtime of AmpliDiff holds back its usability. One time-consuming part is exactly solving a variant of the Set Cover problem. This paper researches whether this exact solution can be replaced by heuristics to reduce the runtime. The Iterated Local Search framework is applied as heuristic and translated onto our problem. After that, it is tested and compared to the original version of the algorithm based on the found solution size. From the results we can deduce that the heuristic version finds the same solutions as the original. It does so in a faster relative time frame as well. However, due to time constraints, the dataset that was used for testing is rather small and therefore not representative of more complex problems, which are usually solved by AmpliDiff. Thus, for future work we recommend to test the heuristics version on a larger, more representative dataset to check its viability. This paper has laid the groundwork by implementing the heuristic and showing that it effectively works for small datasets, giving reason to also try it out on more complicated problems.
...
AmpliDiff is an algorithm for studying environmental samples. As the study of those DNA samples is complicated, the runtime of AmpliDiff holds back its usability. One time-consuming part is exactly solving a variant of the Set Cover problem. This paper researches whether this exact solution can be replaced by heuristics to reduce the runtime. The Iterated Local Search framework is applied as heuristic and translated onto our problem. After that, it is tested and compared to the original version of the algorithm based on the found solution size. From the results we can deduce that the heuristic version finds the same solutions as the original. It does so in a faster relative time frame as well. However, due to time constraints, the dataset that was used for testing is rather small and therefore not representative of more complex problems, which are usually solved by AmpliDiff. Thus, for future work we recommend to test the heuristics version on a larger, more representative dataset to check its viability. This paper has laid the groundwork by implementing the heuristic and showing that it effectively works for small datasets, giving reason to also try it out on more complicated problems.
In this study we introduce a different approach to the primer selection problem in the AmpliDiff [12] algorithm. Two different metrics, being the Hamming distance [2], and the Levenshtein distance [4], are used to compute sets of similar primers. This is done such that locations where mismatches between the primers and the target sequence can occur are determined by the locations of similar primers. The impact that said mismatches have on the solution set of amplicons and their respective primers is outlined. With this we show potential benefits of allowing mismatches to occur, as well as their drawbacks.
...
In this study we introduce a different approach to the primer selection problem in the AmpliDiff [12] algorithm. Two different metrics, being the Hamming distance [2], and the Levenshtein distance [4], are used to compute sets of similar primers. This is done such that locations where mismatches between the primers and the target sequence can occur are determined by the locations of similar primers. The impact that said mismatches have on the solution set of amplicons and their respective primers is outlined. With this we show potential benefits of allowing mismatches to occur, as well as their drawbacks.
AmpliDiff provides a method which takes a list of genomes and their lineages, and finds a set of amplicons and their primers in such a way that these amplicons can be used to differentiate between the lineages of a specific virus. While it has been shown that AmpliDiff find results comparable to whole genome sequencing for SARS-CoV-2 when looking at abundance estimations, it is not know how well it performs for other viruses, or what factors of a virus impacts the performance of the amplicons found by AmpliDiff.\\
In this paper we will be showing the effectiveness of AmpliDiff on Human monkeypox, HIV-1 and Influenza-A.
By running AmpliDiff for the three viruses mentioned above, we obtain sets of amplicons, which are used to do a lineage abundance estimation. By then comparing the estimation to the know abundance we calculate the Mean Average Error (MAE). This MAE will then be used to compare against the MAE obtained from doing a abundance estimation based on whole genome sequencing.
By comparing the amplicons against whole genome sequencing (wgs), we show that using viruses with longer genomes positively impacts the performance of the amplicons. We also show that the amount of misalignment characters added by the Multiple Sequence Alignemnt (MSA), impacts the required settings for AmpliDiff to find amplicons, and can negatively impact the MAE.
Finally, we show that AmpliDiff can be run, with some minor changes to the code base, on segmented genomes, with performance similar to that of single segment genomes. ...
In this paper we will be showing the effectiveness of AmpliDiff on Human monkeypox, HIV-1 and Influenza-A.
By running AmpliDiff for the three viruses mentioned above, we obtain sets of amplicons, which are used to do a lineage abundance estimation. By then comparing the estimation to the know abundance we calculate the Mean Average Error (MAE). This MAE will then be used to compare against the MAE obtained from doing a abundance estimation based on whole genome sequencing.
By comparing the amplicons against whole genome sequencing (wgs), we show that using viruses with longer genomes positively impacts the performance of the amplicons. We also show that the amount of misalignment characters added by the Multiple Sequence Alignemnt (MSA), impacts the required settings for AmpliDiff to find amplicons, and can negatively impact the MAE.
Finally, we show that AmpliDiff can be run, with some minor changes to the code base, on segmented genomes, with performance similar to that of single segment genomes. ...
AmpliDiff provides a method which takes a list of genomes and their lineages, and finds a set of amplicons and their primers in such a way that these amplicons can be used to differentiate between the lineages of a specific virus. While it has been shown that AmpliDiff find results comparable to whole genome sequencing for SARS-CoV-2 when looking at abundance estimations, it is not know how well it performs for other viruses, or what factors of a virus impacts the performance of the amplicons found by AmpliDiff.\\
In this paper we will be showing the effectiveness of AmpliDiff on Human monkeypox, HIV-1 and Influenza-A.
By running AmpliDiff for the three viruses mentioned above, we obtain sets of amplicons, which are used to do a lineage abundance estimation. By then comparing the estimation to the know abundance we calculate the Mean Average Error (MAE). This MAE will then be used to compare against the MAE obtained from doing a abundance estimation based on whole genome sequencing.
By comparing the amplicons against whole genome sequencing (wgs), we show that using viruses with longer genomes positively impacts the performance of the amplicons. We also show that the amount of misalignment characters added by the Multiple Sequence Alignemnt (MSA), impacts the required settings for AmpliDiff to find amplicons, and can negatively impact the MAE.
Finally, we show that AmpliDiff can be run, with some minor changes to the code base, on segmented genomes, with performance similar to that of single segment genomes.
In this paper we will be showing the effectiveness of AmpliDiff on Human monkeypox, HIV-1 and Influenza-A.
By running AmpliDiff for the three viruses mentioned above, we obtain sets of amplicons, which are used to do a lineage abundance estimation. By then comparing the estimation to the know abundance we calculate the Mean Average Error (MAE). This MAE will then be used to compare against the MAE obtained from doing a abundance estimation based on whole genome sequencing.
By comparing the amplicons against whole genome sequencing (wgs), we show that using viruses with longer genomes positively impacts the performance of the amplicons. We also show that the amount of misalignment characters added by the Multiple Sequence Alignemnt (MSA), impacts the required settings for AmpliDiff to find amplicons, and can negatively impact the MAE.
Finally, we show that AmpliDiff can be run, with some minor changes to the code base, on segmented genomes, with performance similar to that of single segment genomes.