Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Efficient enumeration of phylogenetically informative substrings.

Stanislav Angelov1, Boulos Harb, Sampath Kannan

  • 1Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, USA. angelov@cis.upenn.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|August 19, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Generation of spermatid-like cells from testicular biopsies obtained from prepubertal boys.

F&S science·2026
Same author

Dissecting the coordinated progression of cell states in spatial transcriptomics with CoPro.

bioRxiv : the preprint server for biology·2026
Same author

Single-cell Transcriptomic Variance Analysis Reveals Intercellular Circadian Desynchrony in the Alzheimer's Affected Human Brain.

bioRxiv : the preprint server for biology·2026
Same author

Controlling nephron precursor differentiation to generate proximal-biased kidney organoids with emerging maturity.

Nature communications·2025
Same author

Single cell phototransfection of mRNAs encoding SARS-CoV2 spike and nucleocapsid into human astrocytes results in RNA dependent translation interference.

Frontiers in drug delivery·2025
Same author

Lineage-resolved analysis of embryonic gene expression evolution in <i>C. elegans</i> and <i>C. briggsae</i>.

Science (New York, N.Y.)·2025
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

We developed algorithms to find conserved DNA substrings, called tags, unique to specific groups of related genomes within a phylogenetic tree. This aids in identifying evolutionary relationships and conserved genetic elements across species.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Identifying conserved DNA sequences across related species is crucial for understanding evolutionary relationships and identifying functional genomic elements.
  • Phylogenetic trees represent evolutionary descent, but efficiently finding unique shared substrings (tags) within these structures is computationally challenging.

Purpose of the Study:

  • To develop efficient algorithms for enumerating conserved substrings (tags) that are present in one set of genomes but absent in another, within a phylogenetic context.
  • To generalize the concept of tags to sets of substrings for cases where exact tags do not exist.
  • To apply these algorithms to a real-world dataset of microbial genomes.

Main Methods:

  • Developed a near-linear time algorithm for exact tag enumeration.

Related Experiment Videos

  • Proposed a sublinear space algorithm for large datasets.
  • Utilized a stochastic model of evolution to inform a faster, probabilistic tag discovery algorithm.
  • Introduced a linear programming approach for finding approximate generalized tag sets.

    • Main Results:

    • Presented efficient algorithms for discovering genomic tags.
    • Demonstrated that a simple tag-generation process captures essential evolutionary patterns.
    • Successfully applied tag enumeration to a phylogeny of 57 microbial genomes.
    • Identified tags for most nodes and generalized tag sets for the root in the microbial phylogeny.

    Conclusions:

    • The developed algorithms provide powerful tools for identifying conserved genomic elements and understanding evolutionary history.
    • Generalized tag sets offer a robust solution for analyzing phylogenies where exact tags are rare.
    • The study highlights the utility of tag enumeration in comparative genomics and phylogenetic analysis.