Article
Computer Science, Interdisciplinary Applications
Gabriel Siqueira, Alexsandro Oliveira Alexandrino, Zanoni Dias
Summary: Genome rearrangement distance problems estimate the evolutionary distance between genomes. This study introduces a new model considering intergenic regions and multiple copies of genes. It proposes a series of problems and approximation algorithms, and demonstrates their effectiveness through experimental tests.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2023)
Article
Biochemical Research Methods
Klairton Lima Brito, Alexsandro Oliveira Alexandrino, Andre Rodrigues Oliveira, Ulisses Dias, Zanoni Dias
Summary: Most existing mathematical models for genome rearrangement problems consider only gene order, but recent research has started to incorporate more information such as intergenic region sizes. This study investigates a new variation where the target intergenic region sizes have a range of acceptable values, allowing flexibility in transforming gene order while considering variations in intergenic regions. The authors present approximation algorithms and an NP-hardness proof for the problem, relying on the Flexible Weighted Cycle Graph.
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
(2023)
Article
Biochemical Research Methods
Alexsandro Oliveira Alexandrino, Andre Rodrigues Oliveira, Ulisses Dias, Zanoni Dias
Summary: The genome rearrangement field focuses on minimizing the number of genome rearrangements through pairwise genome comparisons. Models should consider gene order, intergenic regions, and types of rearrangement events.
JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY
(2021)
Article
Entomology
Ran Li, Zhiming Lei, Wenjuan Li, Wei Zhang, Changfa Zhou
Summary: Heptageniidae is one of the most abundant and widespread families of mayflies, with ancient mitochondrial genome features. The research findings shed light on its phylogenetic relationships and genetic evolution mechanisms. The mitochondrial genomes of Heptageniidae offer new molecular markers for species identification.
Article
Biochemical Research Methods
Klairton L. Brito, Andre R. Oliveira, Alexsandro O. Alexandrino, Ulisses Dias, Zanoni Dias
Summary: This study investigates the problem of sorting by intergenic reversals and transpositions on genomes with the same set of genes, considering both known and unknown gene orientations. An approximation algorithm is presented that guarantees a factor of 4 for both reversal and transposition events, an improvement from the previously known 4.5-approximation for unknown gene orientations. A 3-approximation algorithm is also proposed for incorporating generalized transposition events, with a greedy strategy to enhance algorithm performance. Practical tests and experiments using real genomes demonstrate the algorithms' applicability and performance improvements.
ALGORITHMS FOR MOLECULAR BIOLOGY
(2021)
Article
Biochemical Research Methods
Alexsandro Oliveira Alexandrino, Klairton Lima Brito, Andre Rodrigues Oliveira, Ulisses Dias, Zanoni Dias
Summary: Recent research has found that incorporating intergenic region information in models along with gene order can provide more accurate estimations for genome rearrangement distance compared to using gene order alone. The reversal distance, a key problem in genome rearrangements, has polynomial time algorithms when only gene order is considered, but becomes NP-hard when intergenic regions are included. In this study, we present a 2.5-approximation algorithm using a labeled intergenic breakpoint graph, and the algorithm's practical approximation factor is found to be significantly less than 2.5 through experimental analysis with simulated data. Additionally, the algorithm is applied to real genomes to construct a phylogenetic tree.
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
(2023)
Proceedings Paper
Computer Science, Theory & Methods
Klairton Lima Brito, Andre Rodrigues Oliveira, Alexsandro Oliveira Alexandrino, Ulisses Dias, Zanoni Dias
Summary: Biologists have proposed a wide range of problems that are heavily studied by mathematicians, computer scientists, and statisticians. Structural modifications like genome rearrangements, including reversal and transposition, are important for comparative genomics. Incorporating information on the size of intergenic regions in genome studies is increasing, aiming to transform a source genome into a target genome.
PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM
(2021)
Article
Biotechnology & Applied Microbiology
Xue-Ying Ge, Tong Liu, Ya Kang, Hao-Yu Liu, Yu-Xia Yang
Summary: This study focuses on an important and unusual subfamily of fireflies, Ototretinae. The authors sequenced and annotated three mitogenomes from this subfamily and discovered a novel gene rearrangement in the Stenocladius species. The phylogenetic analyses also revealed some discrepancies in the evolutionary relationship within the Ototretinae subfamily, requiring further investigation.
Article
Biochemical Research Methods
Alexsandro Oliveira Alexandrino, Andre Rodrigues Oliveira, Geraldine Jean, Guillaume Fertin, Ulisses Dias, Zanoni Dias
Summary: The most common method to calculate the rearrangement distance between genomes is based on the size of a minimum length sequence of rearrangements. Advances in genome rearrangements have led to the consideration of unbalanced genomes and additional genomic characteristics. This study focuses on the Reversal, Transposition, and Indel Distance using intergenic information, including indels in the rearrangement model. An improved 4-approximation algorithm is presented for transpositions and indels on unbalanced genomes, which can also handle gene orientation. Experimental evaluation is conducted using simulated data.
JOURNAL OF COMPUTATIONAL BIOLOGY
(2023)
Article
Entomology
Zhenxing Ma, Ran Li, Binqing Zhu, Xuhongyi Zheng, Changfa Zhou
Summary: This study sequenced 15 mitochondrial genomes of Epeorus and compared them with six available ones in the NCBI database, revealing gene rearrangements and differences in genetic composition and codon usage among species. Phylogenetic analyses indicated that three subgenera, Proepeorus, Belovius, and Iron, are not monophyletic groups.
Article
Biodiversity Conservation
Denis Goryunov, Evgeniia A. Sotnikova, Svetlana Goryunova, Oxana Kuznetsova, Maria D. Logacheva, Irina A. Milyutina, Alina Fedorova, Vladimir E. Fedosov, Aleksey Troitsky
Summary: Polytrichum commune is a widely accepted model for research, with a large mitochondrial genome length. Analysis of pairwise identity in mitochondrial genomes shows distinct differences between Tetraphis pellucida and Buxbaumia aphylla compared to other bryophyte species.
Article
Biochemistry & Molecular Biology
Wei Xu, Jiayu Ding, Shupeng Lin, Runfeng Xu, Hongyi Liu
Summary: A new type of mitochondrial gene arrangement was identified in Moenkhausia, with three new complete mitogenomes sequenced. These mitogenomes exhibited differences in gene order and organization compared to typical teleostean mitogenomes, providing insight into the features of Characidae mitogenomes for further phylogenetic studies. BI and ML analyses classified M. costae and M. pittieri together, with M. sanctaefilomenae slightly farther from other fish in the same genus.
INTERNATIONAL JOURNAL OF BIOLOGICAL MACROMOLECULES
(2021)
Article
Biochemistry & Molecular Biology
Asher Moshe, Elya Wygoda, Noa Ecker, Gil Loewenthal, Oren Avram, Omer Israeli, Einat Hazkani-Covo, Itsik Pe'er, Tal Pupko
Summary: This study developed a probabilistic approach to infer genome rearrangement rate parameters and used an Approximate Bayesian Computation framework for inference. The method can help elucidate the role of genome rearrangement in evolution and simulate genomes with empirical dynamics.
MOLECULAR BIOLOGY AND EVOLUTION
(2022)
Article
Entomology
Yi-Jie Lin, Ling-Na Cai, Yu-Yang Zhao, Hong-Yi Cheng, Kenneth B. Storey, Dan-Na Yu, Jia-Yong Zhang
Summary: In this study, the formation mechanisms of gene rearrangements and LNCRs in Mantodea were explored, providing insights into the phylogenetic relationships within this order. Several novel gene rearrangements were detected, and conserved motifs were identified. The study also supported the monophyly of one family and the paraphyly of another, and identified synapomorphies exclusive to certain clades.
Article
Biochemistry & Molecular Biology
Bo Zhang, Justin C. Havird, Endong Wang, Jiale Lv, Xuenong Xu
Summary: Mitochondrial gene sequences are widely used for phylogenetic inference in animals, with varying levels of gene rearrangements observed among taxa. Some families maintain the ancestral arthropod gene order, while others show highly divergent gene orders, particularly in the case of mites in the family Phytoseiidae. The high degree of mitochondrial gene rearrangement within this family suggests ongoing rearrangements in their mitogenomes.
INTERNATIONAL JOURNAL OF BIOLOGICAL MACROMOLECULES
(2021)
Article
Computer Science, Interdisciplinary Applications
Andre Rodrigues Oliveira, Alexsandro Oliveira Alexandrino, Geraldine Jean, Guillaume Fertin, Ulisses Dias, Zanoni Dias
Summary: Genome Rearrangements is a classic problem in Computational Biology, with different models and rearrangement methods. A new problem called Sorting by Multi-Cut Rearrangements uses k-cut rearrangement to generate new permutations or strings. This paper extends previous work on unsigned permutations and strings to signed permutations, showing complexity and approximation algorithms for different values of k.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2023)
Article
Biochemical Research Methods
Alexsandro Oliveira Alexandrino, Klairton Lima Brito, Andre Rodrigues Oliveira, Ulisses Dias, Zanoni Dias
Summary: Recent research has found that incorporating intergenic region information in models along with gene order can provide more accurate estimations for genome rearrangement distance compared to using gene order alone. The reversal distance, a key problem in genome rearrangements, has polynomial time algorithms when only gene order is considered, but becomes NP-hard when intergenic regions are included. In this study, we present a 2.5-approximation algorithm using a labeled intergenic breakpoint graph, and the algorithm's practical approximation factor is found to be significantly less than 2.5 through experimental analysis with simulated data. Additionally, the algorithm is applied to real genomes to construct a phylogenetic tree.
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
(2023)
Article
Biochemical Research Methods
Klairton Lima Brito, Alexsandro Oliveira Alexandrino, Andre Rodrigues Oliveira, Ulisses Dias, Zanoni Dias
Summary: Most existing mathematical models for genome rearrangement problems consider only gene order, but recent research has started to incorporate more information such as intergenic region sizes. This study investigates a new variation where the target intergenic region sizes have a range of acceptable values, allowing flexibility in transforming gene order while considering variations in intergenic regions. The authors present approximation algorithms and an NP-hardness proof for the problem, relying on the Flexible Weighted Cycle Graph.
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
(2023)
Article
Biochemical Research Methods
Klairton Lima Brito, Andre Rodrigues Oliveira, Alexsandro Oliveira Alexandrino, Ulisses Dias, Zanoni Dias
Summary: This article investigates the solution methods for the gene sorting problem in genome rearrangement field, including cases with known and unknown gene orientations, and considering the non-coding regions between genes. The research results show that the problem is NP-hard regardless of whether gene orientations are known. For the case with known gene orientations, we propose a 2-approximation algorithm, and for the case with unknown gene orientations, we propose a 4-approximation algorithm.
JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY
(2023)
Article
Computer Science, Interdisciplinary Applications
Gabriel Siqueira, Alexsandro Oliveira Alexandrino, Zanoni Dias
Summary: Genome rearrangement distance problems estimate the evolutionary distance between genomes. This study introduces a new model considering intergenic regions and multiple copies of genes. It proposes a series of problems and approximation algorithms, and demonstrates their effectiveness through experimental tests.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2023)
Article
Biochemical Research Methods
Alexsandro Oliveira Alexandrino, Andre Rodrigues Oliveira, Geraldine Jean, Guillaume Fertin, Ulisses Dias, Zanoni Dias
Summary: The most common method to calculate the rearrangement distance between genomes is based on the size of a minimum length sequence of rearrangements. Advances in genome rearrangements have led to the consideration of unbalanced genomes and additional genomic characteristics. This study focuses on the Reversal, Transposition, and Indel Distance using intergenic information, including indels in the rearrangement model. An improved 4-approximation algorithm is presented for transpositions and indels on unbalanced genomes, which can also handle gene orientation. Experimental evaluation is conducted using simulated data.
JOURNAL OF COMPUTATIONAL BIOLOGY
(2023)
Proceedings Paper
Computer Science, Artificial Intelligence
Felipe Lopes de Mello, Gabriel Bianchin de Oliveira, Helio Pedrini, Zanoni Dias
Summary: By the end of 2021, over 200 million proteins with unknown molecular functions were evaluated using Transformer architectures. Machine learning was applied to predict the functions, and the proposed model achieved superior results compared to existing literature.
ARTIFICIAL INTELLIGENCE AND SOFT COMPUTING, ICAISC 2022, PT II
(2023)