You are getting a "sequence number" from a table? Via a Stored Routine? Inside a transaction?
There is no good reason to have "get a seq number" inside a bigger transaction; get it before you START the TRANSACTION.
This change will decrease waits/deadlocks on the sequence table, letting the whole system run faster.
I suspect that will help significantly, but still not prevent all deadlocks. I see a very suspicious
delete from SystemSequence where NextId < _nextId
Is there really any need for more than one row in the table?
These two steps:
UPDATE sequence SET id = LAST_INSERT_ID(id + 1)
WHERE sequence_id = 'MySequenceName' ;
SELECT LAST_INSERT_ID();
Note that LAST_INSERT_ID is session-specific, so is unaffected by other connections.
See, for example,
http://forums.mysql.com/read.php?10,616636,616636
(Even better would be to switch to AUTO_INCREMENT, if possible.)