Research Articles (Computer Science)
http://hdl.handle.net/10019.1/96340
2020-12-04T20:52:59ZComparing leaf and root insertion
http://hdl.handle.net/10019.1/106691
Comparing leaf and root insertion
Geldenhuys, Jaco; Van der Merwe, Brink
We consider two ways of inserting a key into a binary search tree: leaf insertion which is the standard method,
and root insertion which involves additional rotations. Although the respective cost of constructing leaf and root
insertion binary search trees trees, in terms of comparisons, are the same in the average case, we show that in
the worst case the construction of a root insertion binary search tree needs approximately 50% of the number of
comparisons required by leaf insertion.
CITATION: Geldenhuys, J. & Van der Merwe, B. 2009. Comparing leaf and root insertion. South African Computer Journal, 44:30-38, doi:10.18489/sacj.v44i0.21.; The original publication is available at http://sacj.cs.uct.ac.za
2009-01-01T00:00:00ZRevival of the magnetar PSR J1622–4950 : observations with MeerKAT, Parkes, XMM-Newton, Swift, Chandra, and NuSTAR
http://hdl.handle.net/10019.1/106422
Revival of the magnetar PSR J1622–4950 : observations with MeerKAT, Parkes, XMM-Newton, Swift, Chandra, and NuSTAR
Camilo, F.; Serylak, M.; Buchner, S.; Merryfield, M.; Kaspi, V. M.; Archibald, R. F.; Bailes, M.; Jameson, A.; Van Straten, W.; Sarkissian, J.; Reynolds, J. E.; Johnston, S.; Hobbs, G.; Abbott, T. D.; Adam, R. M.; Adams, G. B.; Alberts, T.; Andreas, R.; Asad, K. M. B.; Baker, D. E.; Baloyi, T.; Bauermeister, E. F.; Baxana, T.; Bennett, T. G. H.; Bernardi, G.; Booisen, D.; Booth, R. S.; Botha, D. H.; Boyana, L.; Brederode, L. R. S.; Burge, J. P.; Cheetham, T.; Conradie, J.; Conradie, J. P.; Davidson, D. B.; De Bruin, G.; De Swardt, B.; De Villiers, C.; De Villiers, D. I. L.; De Villiers, M. S.; De Villiers, W.; De Waal, C.; Dikgale, M. A.; Du Toit, G.; Du Toit, L. J.; Esterhuyse, S. W. P.; Fanaroff, B.; Fataar, S.; Foley, A. R.; Foste, G.; Fourie, D.; Gamatham, R.; Gatsi, T.; Geschke, R.; Goedhart, S.; Grobler, T. L.; Gumede, S. C.; Hlakola, M. J.; Hokwana, A.; Hoorn, D. H.; Horn, D.; Horrell, J.; Hugo, B.; Isaacson, A.; Jacobs, O.; Jansen Van Rensburg, J. P.; Jonas, J. L.; Jordaan, B.; Joubert, A.; Joubert, F.; Jozsa, G. I. G.; Julie, R.; Julius, C. C.; Kapp, F.; Karastergiou, A.; Karels, F.; Kariseb, M.; Karuppusamy, R.; Kasper, V.; Knox-Davies, E. C.; Koch, D.; Kotze, P. P. A.; Krebs, A.; Kriek, N.; Kriel, H.; Kusel, T.; Lamoor, S.; Lehmensiek, R.; Liebenberg, D.; Liebenberg, I.; Lord, R. T.; Lunsky, B.; Mabombo, N.; Macdonald, T.; Macfarlane, P.; Madisa, K.; Mafhungo, L.; Magnus, L. G.; Magozore, C.; Mahgoub, O.; Main, J. P. L.; Makhathini, S.; Malan, J. A.; Malgas, P.; Manley, J. R.; Manzini, M.; Marais, L.; Marais, N.; Marais, S. J.; Maree, M.; Martens, A.; Matshawule, S. D.; Matthysen, N.; Mauch, T.; McNally, L. D.; Merry, B.; Millenaar, R. P.; Mjikelo, C.; Mkhabela, N.; Mnyandu, N.; Moeng, I. T.; Mokone, O. J.; Monama, T. E.; Montshiwa, K.; Moss, V.; Mphego, M.; New, W.; Ngcebetsha, B.; Ngoasheng, K.; Niehaus, H.; Ntuli, P.; Nzama, A.; Obies, F.; Obrocka, M.; Ockards, M. T.; Olyn, C.; Oozeer, N.; Otto, A. J.; Padayachee, Y.; Passmoor, S.; Patel, A. A.; Paula, S.; Peens-Hough, A.; Pholoholo, B.; Prozesky, P.; Rakoma, S.; Ramaila, A. J. T.; Rammala, I.; Ramudzuli, Z. R.; Rasivhaga, M.; Ratcliffe, S.; Reader, H. C.; Renil, R.; Richter, L.; Robyntjies, A.; Rosekrans, D.; Rust, A.; Salie, S.; Sambu, N.; Schollar, C. T. G.; Schwardt, L.; Seranyane, S.; Sethosa, G.; Sharpe, C.; Siebrits, R.; Sirothia, S. K.; Slabber, M. J.; Smirnov, O.; Smith, S.; Sofeya, L.; Songqumase, N.; Spann, R.; Stappers, B.; Steyn, D.; Steyn, T. J.; Strong, R.; Struthers, A.; Struthers, A.; Stuart, C.; Sunnylall, P.; Swart, P. S.; Taljaard, B.; Tasse, C.; Taylor, G.; Theron, I. P.; Thondikulam, V.; Thorat, K.; Tiplady, A.; Toruvanda, O.; Van Aardt, J.; Van Balla, T.; Van den Heever, L.; Van der Byl, A.; Van der Merwe, C.; Van der Merwe, P.; Van Niekerk, P. C.; Van Rooyen, R.; Van Staden, J. P.; Van Tonder, V.; Van Wyk, R.; Wait, I.; Walker, A. L.; Wallace, B.; Welz, M.; Williams, L. P.; Xaia, B.; Young, N.; Zitha, S.
New radio (MeerKAT and Parkes) and X-ray (XMM-Newton, Swift, Chandra, and NuSTAR) observations of PSR J1622–4950 indicate that the magnetar, in a quiescent state since at least early 2015, reactivated between 2017 March 19 and April 5. The radio flux density, while variable, is approximately 100× larger than during its dormant state. The X-ray flux one month after reactivation was at least 800× larger than during quiescence, and has been decaying exponentially on a 111 ± 19 day timescale. This high-flux state, together with a radio-derived rotational ephemeris, enabled for the first time the detection of X-ray pulsations for this magnetar. At 5%, the 0.3–6 keV pulsed fraction is comparable to the smallest observed for magnetars. The overall pulsar geometry inferred from polarized radio emission appears to be broadly consistent with that determined 6–8 years earlier. However, rotating vector model fits suggest that we are now seeing radio emission from a different location in the magnetosphere than previously. This indicates a novel way in which radio emission from magnetars can differ from that of ordinary pulsars. The torque on the neutron star is varying rapidly and unsteadily, as is common for magnetars following outburst, having changed by a factor of 7 within six months of reactivation.
CITATION: Camilo, F., et al. 2018. Revival of the magnetar PSR J1622–4950 : observations with MeerKAT, Parkes, XMM-Newton, Swift, Chandra, and NuSTAR. Astrophysical Journal, 856(2):1-11, doi:10.3847/1538-4357/aab35a.; The original publication is available at https://iopscience.iop.org
2018-01-01T00:00:00ZAn assessment of algorithms for deriving failure deterministic finite automata
http://hdl.handle.net/10019.1/104762
An assessment of algorithms for deriving failure deterministic finite automata
Nxumalo, Madoda; Kourie, Derrick G.; Cleophas, Loek; Watson, Bruce W.
Failure deterministic finite automata (FDFAs) represent regular languages more compactly than deterministic finite automata (DFAs). Four algorithms that convert arbitrary DFAs to language-equivalent FDFAs are empirically investigated. Three are concrete variants of a previously published abstract algorithm, the DFA-Homomorphic Algorithm (DHA). The fourth builds a maximal spanning tree from the DFA to derive what it calls a delayed input DFA. A first suite of test data consists of DFAs that recognise randomised sets of finite length keywords. Since the classical Aho-Corasick algorithm builds an optimal FDFA from such a set (and only from such a set), it provides benchmark FDFAs against which the performance of the general algorithms can be compared. A second suite of test data consists of random DFAs generated by a specially designed algorithm that also builds language-equivalent FDFAs, some of which may have non-divergent cycles. These random FDFAs provide (not necessarily tight) lower bounds for assessing the effectiveness of the four general FDFA generating algorithms.
CITATION: Nxumalo, M., et al. 2017. An assessment of algorithms for deriving failure deterministic finite automata. South African Computer Journal, 29(1):43-68, doi:10.18489/sacj.v29i1.456.; The original publication is available at http://sacj.cs.uct.ac.za
2017-01-01T00:00:00ZIdentification of broadly neutralizing antibody epitopes in the HIV-1 envelope glycoprotein using evolutionary models
http://hdl.handle.net/10019.1/95581
Identification of broadly neutralizing antibody epitopes in the HIV-1 envelope glycoprotein using evolutionary models
Lacerda, Miguel; Moore, Penny L.; Ngandu, Nobubelo K.; Seaman, Michael; Gray, Elin S.; Murrell, Ben; Krishnamoorthy, Mohan; Nonyane, Molati; Madiga, Maphuti; Wibmer, Constantinos K.; Sheward, Daniel; Bailer, Robert T.; Gao, Hongmei; Greene, Kelli M.; Karim, Salim S. A.; Mascola, John R.; Korber, Bette T. M.; Montefiori, David C.; Morris, Lynn; Williamson, Carolyn; Seoighe, Cathal; the CAVD-NSDP Consortium
Background
Identification of the epitopes targeted by antibodies that can neutralize diverse HIV-1 strains can provide important clues for the design of a preventative vaccine.
Methods
We have developed a computational approach that can identify key amino acids within the HIV-1 envelope glycoprotein that influence sensitivity to broadly cross-neutralizing antibodies. Given a sequence alignment and neutralization titers for a panel of viruses, the method works by fitting a phylogenetic model that allows the amino acid frequencies at each site to depend on neutralization sensitivities. Sites at which viral evolution influences neutralization sensitivity were identified using Bayes factors (BFs) to compare the fit of this model to that of a null model in which sequences evolved independently of antibody sensitivity. Conformational epitopes were identified with a Metropolis algorithm that searched for a cluster of sites with large Bayes factors on the tertiary structure of the viral envelope.
Results
We applied our method to ID50 neutralization data generated from seven HIV-1 subtype C serum samples with neutralization breadth that had been tested against a multi-clade panel of 225 pseudoviruses for which envelope sequences were also available. For each sample, between two and four sites were identified that were strongly associated with neutralization sensitivity (2ln(BF) > 6), a subset of which were experimentally confirmed using site-directed mutagenesis.
Conclusions
Our results provide strong support for the use of evolutionary models applied to cross-sectional viral neutralization data to identify the epitopes of serum antibodies that confer neutralization breadth.
CITATION: Lacerda, M. et al. 2013. Identification of broadly neutralizing antibody epitopes in the HIV-1 envelope glycoprotein using evolutionary models. Virology Journal, 10:347: doi:10.1186/1743-422X-10-347.; The original publication is available at http://www.virologyj.com/content/10/1/347
2013-12-02T00:00:00Z