Pesho Ivanov 🇺🇦

PhD from ETH Zurich. Introduced A* to sequence alignment

[Pesho Ivanov 🇺🇦 @peshotrie]

Just received my PhD diploma from ETH Zurich for opening the topic of A* for optimal sequence alignment.

My thesis argues that A* is natural for alignment by being heuristically fast and provably optimal. I feel lucky to poke such a fundamental problem yet I have no clue why this wasn't done 40y ago.

https://t.co/MVj6JNa0Ty

[Pesho Ivanov 🇺🇦 @peshotrie]

In addition to my coworkers, I am thankful to the external defense committee which appreciated my work and vouched with their reputation:
@veli_makinen, who gave me careful feedback and future directions,
@pashadag, whose papers influenced me from the beginning of my PhD.

[Pesho Ivanov 🇺🇦 @peshotrie]

Just received my PhD diploma from ETH Zurich for opening the topic of A* for optimal sequence alignment.

My thesis argues that A* is natural for alignment by being heuristically fast and provably optimal. I feel lucky to poke such a fundamental problem yet I have no clue why this wasn't done 40y ago.

https://t.co/MVj6JNa0Ty

[Pesho Ivanov 🇺🇦 @peshotrie]

I dedicate this thesis to my high school teachers:
Svilen Rusev, who introduced me to science, and
@BiserkaYovcheva, who equipped me to research it.

I am also grateful to my advisor @mvechev for insisting on provable algorithms, my co-advisor @gxr for insisting on practicality, my coauthors Beni Bichsel, @HarunMustafa416, @akkah21, @curious_coding, and all the countless folks who supported me on my first steps to a childhood dream of science.❤️

[Pesho Ivanov 🇺🇦 @peshotrie]

@pebope1 All code is public and FOSS:
https://t.co/dbDuGZqvPC - prototype read aligner to pangenome graphs
https://t.co/zc3rZpnJJU - fastest global aligner for long seqs
https://t.co/yuLWjDDHTV - minimalistic repo for global alignment for learning and experimentation

[Pesho Ivanov 🇺🇦 @peshotrie]

SVs are not yet well handled because:
1) for targeted A* search, the seed heuristic has to compensate for each indel letter, so you need potential of 10k seeds for 10kbp indel,
2) edit distance is not really a suitable metric when edits are dependent. one usual approach is to add affine (WiP).

[Pesho Ivanov 🇺🇦 @peshotrie]

@SilasKieser Relevant bioinformatical tasks are read alignment, genetic and genomic comparison, and everything that uses these. Note that most of the currently used algorithms are not optimal so the main benefit compared to them will be not speed but accuracy.

[Pesho Ivanov 🇺🇦 @peshotrie]

A* looks natural for optimal alignment. Previously scaled near-linearly seq.length. Now also scales with error rate.

The LACK of seed matches holds more information than their presence. Don't ignore it :")

[Ragnar {Groot Koerkamp} 🦋 @curious_coding]

@peshotrie and I just finished our paper on exact global alignment using A*.

A*PA is now faster than both Edlib and BiWFA when aligning noisy long reads 🎉
We do this using the 'gap-chaining seed heuristic'. 1/6
https://t.co/bk25O7eygx

[Pesho Ivanov 🇺🇦 @peshotrie]

Alignment types viz 2.0 by @curious_coding and me. thanks for suggestions @pashadag, @chirgjain and @krsahlin!

[Heng Li @lh3lh3]

Types of pairwise sequence alignments. I named extension and global-extension alignment. Let me know if you prefer alternative names or find errors.

[Pesho Ivanov 🇺🇦 @peshotrie]

@pashadag @YannPonty @calkan_cs @briankeating Optimal sequence alignment using A*

[Pesho Ivanov 🇺🇦 @peshotrie]

@gxr indeed, this looks very much needed. could you link to specific alternatives that may be used as laws?

[Pesho Ivanov 🇺🇦 @peshotrie]

@estherbianc that's quite interesting! can we conclude that market participation expands the perceived group for the in-group preference? https://t.co/UmkbheNuQL

[Pesho Ivanov 🇺🇦 @peshotrie]

@curious_coding @nomad421 @XLR @jdidion In fact, the 4^p-ary compressed trie is the data stracture we are developing for AStarix
https://t.co/SxU8XqeCwQ

[Pesho Ivanov 🇺🇦 @peshotrie]

@t_brekalo @curious_coding hey Tvrtko, thanks for the interest! would be great to connect A*PA to C/C++! nevertheless, mind the limitations of our algorithm: in particular, the current implementation is slower than Edlib for short sequences (<1kbp) and A LOT slower for distance seqs (>15% errors).

[Pesho Ivanov 🇺🇦 @peshotrie]

@ianholmes thanks, Ian. it is hilarious if game devs are more familiar with A* than with Dijkstra :"P

[Pesho Ivanov 🇺🇦 @peshotrie]

@nomad421 @XLR In fact, the seed heuristic for A* was first applied to semi-global (RECOMB 2022): https://t.co/ugUZEUAa4W