PubMed Health⌕ Search

PubMed · 15559983

Cone-beam tomography with discrete data sets.

Abstract

Sufficiency conditions for cone-beam data are well known for the case of continuous data collection along a cone-vertex curve with continuous detectors. These continuous conditions are inadequate for real-world data where discrete vertex geometries and discrete detector arrays are used. In this paper we present a theoretical formulation of cone-beam tomography with arbitrary discrete arrays of detectors and vertices. The theory models the imaging system as a linear continuous-to-discrete mapping and represents the continuous object exactly as a Fourier series. The reconstruction problem is posed as the estimation of some subset of the Fourier coefficients. The main goal of the theory is to determine which Fourier coefficients can be reliably determined from the data delivered by a specific discrete design. A Fourier component will be well determined by the data if it satisfies two conditions: it makes a strong contribution to the data, and this contribution is relatively independent of the contribution of other Fourier components. To make these considerations precise, we introduce a concept called the cross-talk matrix. A diagonal element of this matrix measures the strength of a Fourier component in the data, while an off-diagonal element quantifies the dependence or aliasing of two different components. One reasonable approach to system design is to attempt to make the diagonal elements of this matrix large and the off-diagonal elements small for some set of Fourier components. If this goal can be achieved, simple linear reconstruction algorithms are available for estimating the Fourier coefficients. To illustrate the usefulness of this approach, numerical results on the cross-talk matrix are presented for different discrete geometries derived from a continuous helical vertex orbit, and simulated images reconstructed with two linear algorithms are presented.

Explore related subjects

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

H H Barrett, H Gifford. 1994. Cone-beam tomography with discrete data sets.. https://doi.org/10.1088/0031-9155%2F39%2F3%2F012

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

A note on a generalized single step theory for any number of hierarchical genomic matrices.

BACKGROUND: The Single Step algorithm allows combining information from genotyped and un-genotyped individuals, provided they are connected by a pedigree. However, current single step theory is limited to a single list of markers. RESULTS: We present a generalized single step (GSS) method that can accommodate any number of hierarchical molecular datasets (e.g. sequence, high and low density arrays) and pedigree, avoiding imputation. We prove that a similar efficient inversion algorithm exists. The method is recursive, starting with the highest marker density scenario. We illustrate the method with simulation and show that GSS can increase predictive accuracy compared to standard single step. R code is provided so that custom scenarios can be easily compared, either with simulated or real data. CONCLUSION: The method developed generalizes extant single step theory to any number of hierarchical molecular relationship matrices, broadening the scenarios where single step can be applied. A topic of particular interest can be ecology field data or human populations where pedigree is not available, but where samples sequenced and genotyped at different densities can exist. GSS can also be a useful tool to optimize allocation of genotyping and / or sequencing resources.

Algorithms↗

cgDist: Nucleotide-level distance calculation from cgMLST allelic profiles.

Bacterial genomic surveillance requires balancing computational efficiency with genetic resolution for effective cluster investigation. cgMLST distance calculations treat all allelic differences as equivalent units, obscuring nucleotide-level variation. Furthermore, single nucleotide polymorphism-based pipelines provide finer resolution at substantially higher computational cost, which limits their routine deployment in surveillance laboratories. We present cgDist, an algorithm that calculates nucleotide-level distances directly from cgMLST allelic profiles, providing finer resolution than allele-count distances by leveraging within-allele nucleotide variation. The cache architecture stores alignment statistics, enabling distance calculation modes without computation and supporting both dataset-specific and schema-complete cache generation. This design enables incremental surveillance analysis, with performance benefits as laboratories accumulate alignment data. cgDist functions as a precision 'zoom lens' for the investigation of clusters identified through initial cgMLST screening. Rather than restructuring population relationships, this targeted approach concentrates enhanced resolution where it is most informative. The algorithm ensures that cgDist distances are greater than or equal to corresponding cgMLST distances, preserving epidemiological interpretability while adding genetic discrimination. By increasing resolution within identified clusters, cgDist may also support outbreak investigation, a potential application that remains to be evaluated on outbreak-derived data.

Algorithms↗

Theseus: fast and optimal affine-gap sequence-to-graph alignment.

MOTIVATION: Sequence-to-graph alignment is a central problem in bioinformatics, with applications in multiple sequence alignment (MSA) and pangenome analysis, among others. However, current algorithms for optimal affine-gap alignment impose high memory and computational requirements, limiting their scalability to aligning long sequences to complex graphs. Practical solutions partially address this problem using heuristic strategies that ultimately trade off optimality for speed. RESULTS: This work presents Theseus, a novel, fast, and optimal affine-gap sequence-to-graph alignment algorithm. Theseus leverages similarities between genomic sequences to accelerate the alignment computation and reduces the overall memory requirements without compromising optimality. To that end, Theseus processes only a subset of the dynamic programming cells, using a sparse-data strategy that enables efficient sequence-to-graph alignment. Moreover, our algorithm supports optimal affine-gap alignment on arbitrary directed graphs, including those with cycles. We evaluate Theseus on two key problems: MSA and pangenome read mapping. For MSA, we compare it against SPOA, abPOA, and POASTA. Theseus is 1.6× to 17.6× faster than POASTA, and 7.3× faster, on average, than SPOA, both optimal aligners. Compared with abPOA, Theseus ensures optimality and scales to the largest problems. For pangenome read mapping, we benchmark Theseus against the alignment stage of the mapping tool vg map, along with the alignment kernels of SPOA, abPOA, and POASTA. Theseus outperforms the other methods, showing a 1.9× to 16.9× speedup on short reads. Moreover, Theseus is 1.5× to 36.3× faster than vg when aligning against synthetic cyclic graphs. AVAILABILITY AND IMPLEMENTATION: Theseus code and documentation are publicly available at https://github.com/albertjimenezbl/theseus-lib.

Algorithms↗